712. 两个字符串的最小ASCII删除和
class MinimumDeleteSum:
"""
712. 两个字符串的最小ASCII删除和
https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/
"""
def solution(self, s1: str, s2: str) -> int:
"""
递归解法 + 备忘录
自顶向下
:param text1:
:param text2:
:return:
"""
m, n = len(s1), len(s2)
self.memo = [[-1 for _ in range(n)] for _ in range(m)]
return self.dp(s1, 0, s2, 0)
def dp(self, text1, i, text2, j):
"""
将 s1[i..] 和 s2[j..] 删除成相同字符串
:param text1:
:param i:
:param text2:
:param j:
:return:
"""
res = 0
# base case
if i == len(text1):
while j < len(text2):
res += ord(text2[j])
j += 1
return res
if j == len(text2):
while i < len(text1):
res += ord(text1[i])
i += 1
return res
# 备忘录
if self.memo[i][j] != -1:
return self.memo[i][j]
if text1[i] == text2[j]:
self.memo[i][j] = self.dp(text1, i + 1, text2, j + 1)
else:
self.memo[i][j] = min(self.dp(text1, i + 1, text2, j) + ord(text1[i]),
self.dp(text1, i, text2, j + 1) + ord(text2[j]))
return self.memo[i][j]