712.md

712 Minimum ASCII Delete Sum for Two Strings

Description

link

---

Solution

这题的关键在于一个逆向思维，求删除掉的不同字符，我们可以反过来求相同的字符的 ASCII 总和，最后剪掉两次这个和即可

dp[i][j] : the sum of the same characters from s1[:i] and s2[:j]

Recursive :

• if s1[i] == s2[j]: dp[i + 1][j + 1] = dp[i][j] + ord(s1[i])
• else: dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

Init : all 0

---

Code

Complexity T : O(len1 * len2) M : O(len1 * len2)

class Solution:
    def minimumDeleteSum(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: int
        """
        len1, len2 = len(s1), len(s2)
        
        dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
        
        for i in range(len1):
            for j in range(len2):
                if s1[i] == s2[j]:
                    dp[i + 1][j + 1] = dp[i][j] + ord(s1[i])
                else:
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
            
        res = sum([ord(x) for x in s1 + s2]) - dp[len1][len2] * 2
        return res