583. 两个字符串的删除操作
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n, m = len(word1), len(word2)
# dp 数组代表使得 word1 以 i-1 结尾和 word2 以 j-1 结尾相同的最小步数
dp = [[0] * (m+1) for _ in range(n+1)]
# 初始化
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = j
for i in range(1, n+1):
for j in range(1, m+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 2)
return dp[n][m]
72. 编辑距离
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n, m = len(word1), len(word2)
# dp 数组代表以 i-1 结尾的 word1 变成 以 j-1 结尾的 word2 的最小操作数为 dp[i][j]
dp = [[0] * (m+1) for _ in range(n+1)]
# 初始化
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = j
for i in range(1, n+1):
for j in range(1, m+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
return dp[n][m]