编辑距离
Edit Distance
本机进度仅保存在当前浏览器
题目描述
给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。可以对一个单词进行三种操作：插入一个字符、删除一个字符、替换一个字符。
示例：word1 = "horse"，word2 = "ros"，输出 3（horse -> rorse -> rose -> ros）。
解题思路
- 状态 dp[i][j]：word1 前 i 个字符变成 word2 前 j 个字符的最少操作数。
- 末字符相等时免费继承 dp[i-1][j-1]；不等时在「删、插、改」三种操作中取最小再加一。
- 边界是空串情形：dp[i][0] = i（全删）、dp[0][j] = j（全插）；该状态定义同时给出了边界含义。
参考实现
查看参考实现Python · 建议先自行作答
def minDistance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], # 删除
dp[i][j - 1], # 插入
dp[i - 1][j - 1]) # 替换
return dp[m][n]