力扣第 583 题
题目
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1：
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
示例 2:
输入：word1 = "leetcode", word2 = "etco"
输出：4
提示：
1 <= word1.length, word2.length <= 500word1 和 word2 只包含小写英文字母
相似问题：
分析
#1
按末尾是否删除递推即可。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m,n = len(word1),len(word2)
f = [list(range(n+1)) for _ in range(m+1)]
for i in range(1,m+1):
f[i][0] = i
for j in range(1,n+1):
if word1[i-1]==word2[j-1]:
f[i][j] = f[i-1][j-1]
else:
f[i][j] = 1+min(f[i-1][j],f[i][j-1])
return f[-1][-1]
|
175 ms
#2
还可以用滚动数组优化空间。
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m,n = len(word1),len(word2)
f = list(range(n+1))
for c in word1:
g = f[:]
f[0] += 1
for j in range(1,n+1):
if c==word2[j-1]:
f[j] = g[j-1]
else:
f[j] = 1+min(g[j],f[j-1])
return f[-1]
|
143 ms