Leetcode712.MinimumASCIIDeleteSumforTwoStrings

Problem

Given two strings s1 and s2, return the lowest ASCII sum of deleted characters to make two strings equal.

Algorithm

Dynamic Programming (DP): similar as Longest Common Subsequence (LCS).

If s1[i] != s2[j]: F ( i , j ) = min ⁡ ( F ( i − 1 , j ) + cost ( s 1 [ i ] ) ,   F ( i , j − 1 ) + cost ( s 2 [ j ] ) ) F(i, j) = \min \left( F(i-1, j) + \text{cost}(s1[i]), \, F(i, j-1) + \text{cost}(s2[j]) \right) F(i,j)=min(F(i−1,j)+cost(s1[i]),F(i,j−1)+cost(s2[j]))

If s1[i] == s2[j]: F ( i , j ) = F ( i − 1 , j − 1 ) F(i, j) = F(i-1, j-1) F(i,j)=F(i−1,j−1)

Code class Solution: def minimumDeleteSum(self, s1: str, s2: str) -> int: l1, l2 = len(s1) + 1, len(s2) + 1 dp = [[0] * l2 for _ in range(l1)] for i in range(1, l1): dp[i][0] = dp[i-1][0] + ord(s1[i-1]) for j in range(1, l2): dp[0][j] = dp[0][j-1] + ord(s2[j-1]) for i in range(1, l1): for j in range(1, l2): if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])) return dp[l1-1][l2-1]