712. Minimum ASCII Delete Sum for Two Strings

712. Minimum ASCII Delete Sum for Two Strings

概念和 1143. Longest Common Subsequence 很類似，要注意的地方不同而已。

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:

        @lru_cache(None)
        def helper(i, j):
            if i == len(s1) and j == len(s2):
                return 0
            elif i == len(s1):
                ans = 0
                while j < len(s2):
                    ans += ord(s2[j])
                    j += 1
                return ans
            elif j == len(s2):
                ans = 0
                while i < len(s1):
                    ans += ord(s1[i])
                    i += 1
                return ans
            elif s1[i] == s2[j]:
                return helper(i+1, j+1)
            else:
                return min(ord(s1[i]) + helper(i+1, j), ord(s2[j]) + helper(i, j+1))

        return helper(0, 0)