題目

LeetCode - 712. Minimum ASCII Delete Sum for Two Strings

解題思路

給出两個字符串，可以在每個字符串中删除一些字符，得到相等的字符串。求删除的字符的ASCII最小和。這題使用dp[i][j] = lowest ASCII sum of deleted characters to make s1[0:i]==s2[0:j]的想法去做就可以了。

Code

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
class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        # dp[i][j] =  lowest ASCII sum of deleted characters to make s1[0:i]==s2[0:j] 
        # ord(str) 將數字轉為ASCii
        m = len(s1)
        n = len(s2)
        s1 = '#'+s1
        s2 = '#'+s2
        dp = [[0 for _  in range(n+1)] for _ in range(m+1)]

        #dp[0][0] = 0
        for i in range(1,m+1):
             dp[i][0] = ord(s1[i]) + dp[i-1][0] 
                
        for j in range(1,n+1):
             dp[0][j] = ord(s2[j]) + dp[0][j-1] 
          
        for i in range(1,m+1):
            for j in range(1,n+1):
                if s1[i] == s2[j]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j]+ord(s1[i]) , dp[i][j-1]+ord(s2[j]))
        
        return dp[m][n]