题目
Given two strings word1
and word2
, return the minimum number of steps required to make word1
and word2
the same.
In one step, you can delete exactly one character in either string.
Example 1:
Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Example 2:
Input: word1 = "leetcode", word2 = "etco"
Output: 4
Constraints:
1 <= word1.length, word2.length <= 500
word1
andword2
consist of only lowercase English letters.
思路
为word1和word2分别设两个指针i、j进行遍历,总共分为如下几种情况:
- i遍历到底且j遍历到底:无需删除任何字符。
- i遍历到底或j遍历到底:有一方已经遍历到底,需删除一方剩余的字符。
- i和j所标识的字符相等:当前字符相等,无需删除,i和j均前进一步。
- i和j所标识的字符不相等:分为删除i字符或删除j字符两种情况,随后删除的一方前进一步。
代码
python版本:
# dfs,超时
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
def dfs(i, j):
if i == len(word1) and j == len(word2):
return 0
if i == len(word1) or j == len(word2):
return len(word1)+len(word2)-i-j
if word1[i] == word2[j]:
return dfs(i+1, j+1)
return min(dfs(i+1, j), dfs(i, j+1))+1
return dfs(0, 0)
# 优化dfs,使用辅助数组记录重复调用 1255 ms
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
helper = [[-1]*len(word2) for _ in range(len(word1))]
def dfs(i, j):
print(i, j)
if i == len(word1) and j == len(word2):
return 0
if i == len(word1) or j == len(word2):
return len(word1)+len(word2)-i-j
if helper[i][j] != -1:
return helper[i][j]
if word1[i] == word2[j]:
helper[i][j] = dfs(i+1, j+1)
return helper[i][j]
helper[i][j] = min(dfs(i+1, j), dfs(i, j+1))+1
return helper[i][j]
res = dfs(0, 0)
return res
# 动态规划 320 ms
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [[math.inf]*(len(word2)+1) for _ in range(len(word1)+1)]
for i in range(len(dp)):
for j in range(len(dp[i])):
if i == 0 or j == 0:
dp[i][j] = i or j
elif word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1])+1
return dp[-1][-1]