编辑距离
编辑距离是针对二个 字符串（例如英文字）的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。在莱文斯坦距离中，可以删除、加入、替换字符串中的任何一个字元，也是较常用的编辑距离定义，常常提到编辑距离时，指的就是莱文斯坦距离。
怎么求解莱文斯坦距离？如果使用暴力的解法枚举每一种可能，将是指数级的复杂度。它可以使用动态规划的方式进行求解，状态转移方程为：
其中\(a,b\)是两个字符串，\(|a|\)表示a的长度，\(head(a)\)表示\(a\)的首字符，\(tail(a)\)表示\(a\)除了首字符之外剩下的字符。如何理解呢？
- 第一行和第二行很好理解，如果一个字符串为空，那就只能插入另一个字符串。
- 第三行，如果首字符如果一样，那就是剩下部分的编辑距离。
- 第四行，分类讨论。如果首字符不一样：
- 删除a的首字符，再加上剩下部分的编辑距离。
- 删除b的首字符，再加上剩下部分的编辑距离。
- 替换某个字符串的首字符，让首字符一样，再加上剩下部分的编辑距离。
动态规划的代码如下：
def minDistance(s1, s2):
m,n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(0,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 s1[i-1] == s2[j-1]:
# 当前字符相同，无需操作
dp[i][j] = dp[i-1][j-1]
else:
# 取替换、删除、插入中的最小操作数+1
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
return dp[m][n]
72. 编辑距离 - 力扣（LeetCode） 就是要求解编辑距离，解法如下，使用记忆化搜索来防止重复求解子问题。
from functools import cache
class Solution:
@cache
def minDistance(self, word1: str, word2: str) -> int:
if len(word1) == 0:
return len(word2)
if len(word2) == 0:
return len(word1)
if word1[0] == word2[0]:
return self.minDistance(word1[1:], word2[1:])
return 1+min(self.minDistance(word1[1:], word2), self.minDistance(word1, word2[1:]), self.minDistance(word1[1:], word2[1:]))