Leetcode Link: 72. 编辑距离 - 力扣（LeetCode）
题目
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
从暴力递归到动态规划
暴力递归
本题乍一看不好分析，实际上就是看题，然后直接按照题意进行自然智慧的思考
本题采用样本对应模型，子函数参数为 (i, j)，分别表示 word1[0...i] 变成 word2[0...j] 的最少操作数
本题难在分析普通位置的情况，我们就直接按照题意分析，假定在任意结尾位置 (i, j) 处，我们执行 3 种操作（插入、删除、替换），同时一定记得如果相等，可以不做操作。
即总计四种情况：
- 无操作，有前提，需要
word1[i] == word2[j] - 删除操作，执行删除操作，一定是删除的
word1[i]，也就是说我们还没找到word2[j]，所以操作数+1， i—, j 不变 - 替换操作，即替换了
word1[i]并令其等于word2[j]，那么下面就可以看 j-1 和 i-1 了，但是实际上我们这里执行了一次操作，故操作数+1，i—, j— - 插入操作，一定要想清楚我们插入在那个位置，我们一定是在 i+1 位置插入的，word1 [i] 相当于还没留到下一次看（虽然此时 i+1 已经走过去了，但是不影响我们分析题目）。那么此时插入的一定是和 word2 [j]相等的，因此 j—，i 不变，同时操作数+1
base case 很好分析
- 当 i <0，同时j> =0, 即 word1 已经为空，但是 word2 不为空，此时只能一直向word1种插入至等于word2
- 当 i >=0，同时 j<0，此时只能一直删除至空
- 当两者都为空，两者相等，即不需要操作数，返回0
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
# word1 --> word2
def process(i, j):
if i<0 and j>=0:
return j+1
if j<0 and i>=0:
return i+1
if j<0 and i<0:
return 0
p1 = float('inf')
if word1[i] == word2[j]:
p1 = process(i-1, j-1)
p2 = process(i-1, j) + 1 # 删除
p3 = process(i-1, j-1) + 1 # 替换
p4 = process(i, j-1) + 1 # 插入
return min(p1, p2, p3, p4)
return process(len(word1)-1, len(word2)-1)a暴力递归改进
我们要注意，不等号的 base case，在写成 dp 的时候，边界判定会很麻烦，因此这里我们尝试将其改写成等号的 base case 并加以解释。
如果是等号，则只能等于 0，这是毋庸置疑的。
- 当
i==0，表示 word1 只剩最后一个字符的时候，如果 word1 [0]在 word2 [0.. j] 中，则只需要插入；反之，若 word1 [0]不在 word2 [0.. j] 中，则需要插入，并将替换一次 - 当
j==0，分析同上，不过替换变成了删除。
但是，在这种 base case 下，由于空字符串的长度为 0 (len("")==0)，故当索引为 0 的时候会溢出边界，导致报错，所以需要在开始的时候进行特例判定。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
# word1 --> word2
memo = {}
def process(i, j):
if i==0:
if word1[0] in word2[0:j+1]:
return j # 插入
else:
return j + 1 # 插入+替换
if j==0:
if word2[0] in word1[0:i+1]:
return i # 只需要删除
else:
return i + 1 # 删除+替换
if (i,j) in memo.keys():
return memo[(i,j)]
p1 = float('inf')
try:
if word1[i] == word2[j]:
p1 = process(i-1, j-1)
except:
return (i, j)
p2 = process(i-1, j) + 1 # 删除
p3 = process(i-1, j-1) + 1 # 替换
p4 = process(i, j-1) + 1 # 插入
memo[(i,j)] = min(p1, p2, p3, p4)
return min(p1, p2, p3, p4)
# 特例判定
if word1 == "":
return len(word2)
if word2 == "":
return len(word1)
return process(len(word1)-1, len(word2)-1)动态规划
直接抄就行，改写出来后有点像两个字符串的删除操作的味道。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
if word1 == "":
return len(word2)
if word2 == "":
return len(word1)
dp = [[0 for _ in range(len(word2))] for _ in range(len(word1))]
for j in range(len(word2)):
if word1[0] in word2[0:j+1]:
dp[0][j] = j # 删除
else:
dp[0][j] = j + 1 # 删除+替换
for i in range(len(word1)):
if word2[0] in word1[0:i+1]:
dp[i][0] = i # 只需要插入
else:
dp[i][0] = i + 1 # 插入+替换
for i in range(1, len(word1)):
for j in range(1, len(word2)):
p1 = float('inf')
if word1[i] == word2[j]:
p1 = dp[i-1][j-1]
p2 = dp[i-1][j] + 1 # 删除
p3 = dp[i-1][j-1] + 1 # 替换
p4 = dp[i][j-1] + 1 # 插入
dp[i][j] = min(p1, p2, p3, p4)
return dp[-1][-1]