leetcode-712-两个字符串的最小ASCII删除和

发表于 阅读次数： 本文字数： 749 阅读时长 ≈ 1 分钟
简介：leetcode-712-两个字符串的最小ASCII删除和

题目

https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/description/?envType=study-plan-v2&envId=dynamic-programming

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m,n = len(s1),len(s2)

        # 最大ASCCII子序和
        lst = [[0 for j in range(n)] for i in range(m)]

        # 初始化
        if s1[0] == s2[0]:
            lst[0][0] = ord(s1[0])
        for i in range(1,m):
            if s1[i] == s2[0]:
                lst[i][0] = ord(s1[i])
            else:
                lst[i][0] = lst[i-1][0]
        for j in range(1,n):
            if s1[0] == s2[j]:
                lst[0][j] = ord(s2[j])
            else:
                lst[0][j] = lst[0][j-1]
        
        # 状态转移
        for i in range(1,m):
            for j in range(1,n):
                if s1[i] == s2[j]:
                    lst[i][j] = ord(s1[i]) + lst[i-1][j-1]
                else:
                    lst[i][j] = max(lst[i-1][j],lst[i][j-1])
        # print(lst)
        return sum(map(ord,s1))+sum(map(ord,s2)) - 2*lst[m-1][n-1]

思路

先找出公共最大ASCII值的子序列（子序列不一定连续，但是顺序不能改变）