0072 - Edit Distance
题干
破题
典型地套题，这类题目几乎只有一种解法，而且不太容易从直觉算法推出，如果不得要领、误入歧途，就会觉得很难，但如果找到路径，就很容易，缺乏变化。就像对待前面的另一个套题： 0053 - Maximum Subarray 一样，LeetCode 也给它 Medium 难度，而我总是认为应当放到 Hard 难度，因为并不是题目本身简单，而只是著名、流行、有模板。
解①DP：
Top-down
或者说递归地解法。
一般来说递归地实现总是最易于理解，但这里并不是这样的。
想象下从头开始比较两个串，姑且命名为 $s_1$ 和 $s_2$ ，如果开始的字符恰好相等，是不是只需要比较 $s_1[1\dots]$ 和 $s_2[1\dots]$ 就可以了？ 1 如果不相等，就需要考虑对 $s_1$ 插入一个字符、删除一个字符、或者替换一个字符，来让第一个字符相等：
- 如果是插入一个字符，那就要在 $s_1$ 队头插入 $s_2[0]$，这时 $s_1$ 和 $s_2[1\dots]$ 对齐，继续递归地比较；
- 如果是删除一个字符，那就要删除 $s_1[0]$ ，这时 $s_1[1\dots]$ 和 $s_2$ 对齐，继续递归比较；
- 如果是替换一个字符，那就是把 $s_1[0]$ 替换为 $s_2[0]$，这时 $s_1[1\dots]$ 和 $s_2[1\dots]$ 对齐，就像递归比较
需要比较地就是这三种操作的最小操作数。
而递归地过程在 $s_1$ 或 $s_2$ 至少任意一个变成空串时返回，当空串出现时操作就只剩下一种可能，就是 $s_1$ 插入或者删除非空串数量的字符2。
当然我们需要缓存递归过程中的计算结果，以避免不必要地重复计算。
时间复杂度 $O(nm)$ ，空间复杂度 $O(nm)$ 。
from functools import cache
@cache
def solve(word1: str, word2: str) -> int:
if len(word1) > len(word2):
word1, word2 = word2, word1
if not word1:
return len(word2)
if not word2: # both empty
return 0
return min(
# insert char
1 + solve(word1, word2[1:]),
# remove char
1 + solve(word1[1:], word2),
# replace char
(0 if word1[0] == word2[0] else 1) + solve(word1[1:], word2[1:])
)
运行时间：448 ms (beats 5.1 %)，内存占用：105 MB (beats 5.76 %) 。
Bottom-up
或者说迭代地版本。
如果要展开递归地版本，应该是从两个字符串的尾部开始反推，但是那样代码写起来有些别扭，从正面开始也一样，而且“更有相似度”。
def solve(word1: str, word2: str) -> int:
if len(word1) > len(word2):
word1, word2 = word2, word1
n = len(word1)
m = len(word2)
cache = [0] * (n+1)
for i in range(1, n+1):
cache[i] = i
for j in range(1, m+1):
prev1 = cache[0]
cache[0] = j
for i in range(1, n+1):
prev0 = cache[i]
if word1[i-1] == word2[j-1]:
cache[i] = prev1
else:
ans_insert = 1+prev0
ans_remove = 1+cache[i-1]
ans_replace = 1+prev1
cache[i] = min(ans_insert, ans_remove, ans_replace)
prev1 = prev0
return cache[-1]
这个代码既视感很强啊，这不完全就是我们 0010 - Regular Expression Matching 和 0044 - Wildcard Matching 的代码吗？
运行时间：106 ms (beats 81.08%)，16.31 MB (beats 96.93%) 。
注解
