JZX轻语：简
LeetCode 712 - 两个字符串的最小ASCII删除和
发表于2024年04月18日
带权重的编辑问题，其中删除一个字符的成本为字符的ASCII值。令dp[i][j]为子串s1[:i]和s2[:j]的最小编辑距离：如果s1[i - 1]等于s2[j - 1]，则dp[i][j] = dp[i - 1][j - 1](两字符串该字符无需修改)，否则dp[i][j] = min(dp[i][j - 1] + ord(s2[j - 1]), dp[i - 1][j] + ord(s1[i - 1]))(删除s1[:i]的最后一个字符的代价 + 子串s1[:i - 1]和s2[:j]的累积代价 or 删除s2[:j]的最后一个字符的代价 + 子串s1[:i]和s2[:j - 1]的累积代价)。
class Solution:
def minimumDeleteSum(self, s1: str, s2: str) -> int:
# dp[i][j] -> s1[:i]和s2[:j]的编辑距离
dp = [[0] * (len(s2) + 1) for _ in range((len(s1) + 1))]
for i, ch in enumerate(s1):
dp[i + 1][0] = dp[i][0] + ord(ch)
for i, ch in enumerate(s2):
dp[0][i + 1] = dp[0][i] + ord(ch)
for i in range(1, len(s1) + 1):
for j in range(1, len(s2) + 1):
c1 = s1[i - 1]
c2 = s2[j - 1]
if c1 == c2:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(
dp[i - 1][j] + ord(c1),
dp[i][j - 1] + ord(c2)
)
return dp[len(s1)][len(s2)]