当前位置：首页 > article >正文

Leetcode 712. Minimum ASCII Delete Sum for Two Strings

article 2025/2/24 10:31:21

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]:
$\min \left( F(i-1, j) + \text{cost}(s1[i]), \, F(i, j-1) + \text{cost}(s2[j]) \right)$
If s1[i] == s2[j]:
$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]