23.07.31 Today’s Leetcode

712. Minimum ASCII Delete Sum for Two Strings

DFS Solution, Failed with 26:32

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        
        n1, n2 = len(s1), len(s2)
        print(ord('s'))

        def dfs(a, b, sa, sb):
            nonlocal n1, n2
            if a == n1:
                if sa == sb:
                    return sum(ord(s2[x]) for x in range(b, n2))
                return math.inf
            if b == n2:
                if sa == sb:
                    return sum(ord(s1[x]) for x in range(a, n1))
                return math.inf
            temp = math.inf
            if sa == sb:
                temp = 0
                temp += sum(ord(s1[y]) for y in range(a, n1))
                temp += sum(ord(s2[x]) for x in range(b, n2))
            
            print(temp)
            
            # delete both
            temp = min(temp, dfs(a + 1, b + 1, sa, sb) + ord(s1[a]) + ord(s2[b]))        

            # delete s1
            temp = min(temp, dfs(a + 1, b, sa, sb + s2[b]) + ord(s1[a]))

            # delete s2
            temp = min(temp, dfs(a, b + 1, sa + s1[a], sb) + ord(s2[b]))

            return temp
        
        res = dfs(0, 0, '', '')

        return res

DP Solution

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        if len(s1) > len(s2):
            s1, s2 = s2, s1
        prev_row = [0] * (len(s2) + 1) 
        for j in range(1, len(s2) + 1): 
            prev_row[j] = prev_row[j - 1] + ord(s2[j - 1]) 

        for i in range(1, len(s1) + 1): 
            curr_row = [prev_row[0] + ord(s1[i - 1])] 
            for j in range(1, len(s2) + 1): 
                if s1[i - 1] == s2[j - 1]: 
                    curr_row.append(prev_row[j - 1]) 
                else: 
                    curr_row.append(min(prev_row[j] + ord(s1[i - 1]), curr_row[j - 1] + ord(s2[j - 1]))) 
            prev_row = curr_row 

        return prev_row[-1]