Leetcode 0712 Minimum ASCII Delete Sum for Two Strings

Problem statement

https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/

Solution

We can solve this problem with dp, if we denote by dp[i][j] the answer for s1[:i] and s2[:j].

Complexity

Time and space complexity is O(mn). Space complexity can be reduced to O(m+n).

Code 1

class Solution:
    def minimumDeleteSum(self, s1, s2):
        s1, s2 = [0] + [ord(i) for i in s1], [0] + [ord(i) for i in s2]
        n1, n2 = len(s1), len(s2)
        dp = [[0] * n2 for _ in range(n1)]

        for i1 in range(1,n1): dp[i1][0] = dp[i1-1][0] + s1[i1]
        for i2 in range(1,n2): dp[0][i2] = dp[0][i2-1] + s2[i2]
            
        for i1 in range(1, n1):
            for i2 in range(1, n2):
                if s1[i1] == s2[i2]:
                    dp[i1][i2] = dp[i1-1][i2-1]
                else:
                    dp[i1][i2] = min(dp[i1-1][i2] + s1[i1], dp[i1][i2-1] + s2[i2])
                
        return dp[-1][-1]

Code 2

class Solution:
    def minimumDeleteSum(self, s1, s2):
        s1, s2 = [0] + [ord(i) for i in s1], [0] + [ord(i) for i in s2]
        n1, n2 = len(s1), len(s2)
        
        @lru_cache(None)
        def dp(i1, i2):
            if i1 == 0 and i2 == 0: return 0
            if i1 == 0: return dp(i1, i2-1) + s2[i2]
            if i2 == 0: return dp(i1-1, i2) + s1[i1]
            if s1[i1] == s2[i2]: return dp(i1-1, i2-1)
            return min(dp(i1-1, i2) + s1[i1], dp(i1, i2-1) + s2[i2])
        
        return dp(n1 - 1, n2 - 1)

Remark

See also similar problem 0072 Edit distance.