Leetcode 712 Solution

This article provides solution to leetcode question 712 (minimum-ascii-delete-sum-for-two-strings)
Categories:
Tags:
Access this page by simply typing in "lcs 712" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m = len(s1)
        n = len(s2)

        dp = [[10000000] * n for _ in range(m)]

        dp[0][0] = 0 if s1[0] == s2[0] else ord(s1[0]) + ord(s2[0])

        s = ord(s1[0])
        for i in range(1, m):
            if s1[i] == s2[0]:
                dp[i][0] = s
            dp[i][0] = min(dp[i][0], ord(s1[i]) + dp[i - 1][0])
            s += ord(s1[i])

        s = ord(s2[0])
        for j in range(1, n):
            if s1[0] == s2[j]:
                dp[0][j] = s
            dp[0][j] = min(dp[0][j], ord(s2[j]) + dp[0][j - 1])
            s += ord(s2[j])

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

        return dp[-1][-1]