题目大意，给定两个单词，问最少需要多少步能把单词1修改成单词2
大概思路:比较word1和word2的最后一个字母：
如果相同，去掉最后一个字母，再比较去掉最后一位以后的两个单词的最后一个字母。
如果不相同，那么有三种子问题：
把word1去掉最后一个字母，然后再转为word2
把word2去掉最后一个字母，然后再转为word1
把word1和word2都去掉最后一个字母，然后再转换
用 \(d(i, j) = minDistance(word1[0 ... i-1], word2[0 ... j-1])\), 即把word1前i个字母转换成word2前j个字母需要的最小edit distance。 那么
d(i, j) =
i if j == 0
j if i == 0
d(i - 1, j - 1) if word1[i - 1] == word2[j - 1]
min(d(i - 1, j), d(i, j - 1), d(i - 1, j - 1)) + 1
1. 记忆化递归
class Solution(object):
def minDistance(self, word1, word2):
m = len(word1)
n = len(word2)
self.d = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]
def helper(word1, word2, m, n):
if m == 0:
return n
if n == 0:
return m
if self.d[m][n] >= 0:
return self.d[m][n]
if word1[m - 1] == word2[n - 1]:
ans = helper(word1, word2, m - 1, n - 1)
else:
ans = min(helper(word1, word2, m - 1, n - 1), helper(word1, word2, m - 1, n), helper(word1, word2, m, n - 1)) + 1
self.d[m][n] = ans
return self.d[m][n]
return helper(word1, word2, m, n)
2. 递推/动态规划
class Solution(object):
def minDistance(self, word1, word2):
m = len(word1)
n = len(word2)
d = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(1, m + 1):
d[i][0] = i
for j in range(n + 1):
d[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
d[i][j] = d[i - 1][j - 1]
else:
d[i][j] = min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]) + 1
return d[m][n]