題目鏈接
給定兩個單詞?word1?和?word2?，返回使得?word1?和??word2?**相同所需的最小步數(shù)。
每步?可以刪除任意一個字符串中的一個字符。
示例 1：
輸入: word1 = "sea", word2 = "eat"
輸出: 2
解釋: 第一步將 "sea" 變?yōu)?"ea" ，第二步將 "eat "變?yōu)?"ea"
示例 ?2:
輸入：word1 = "leetcode", word2 = "etco"
輸出：4
提示：
1 <= word1.length, word2.length <= 500-
word1?和?word2?只包含小寫英文字母
我們可以定義一個二維數(shù)組dp，其中dp[i][j]表示將word1的前i個字符轉(zhuǎn)換為word2的前j個字符所需的最小步數(shù)。
首先，我們需要考慮邊界情況，當(dāng)word1和word2的長度分別為零時，它們已經(jīng)相同了，所以dp[0][0] = 0。當(dāng)word1為空字符串，而word2不為空時，則需要刪除word2中的所有字符，所以dp[0][j] = j。同理，當(dāng)word2為空字符串，而word1不為空時，需要刪除word1中的所有字符，所以dp[i][0] = i。
接下來，我們考慮狀態(tài)轉(zhuǎn)移方程。假設(shè)我們要計算dp[i][j]，即將word1的前i個字符轉(zhuǎn)換為word2的前j個字符所需的最小步數(shù)。我們有以下幾種情況：
-
如果
word1[i-1]等于word2[j-1]，即當(dāng)前字符相等，那么不需要進行刪除操作，所以dp[i][j] = dp[i-1][j-1]。 -
如果
word1[i-1]和word2[j-1]不相等，那么我們有兩種選擇：文章來源：http://www.zghlxwxcb.cn/news/detail-609058.html- 刪除
word1[i-1]字符，然后將word1的前i-1個字符轉(zhuǎn)換為word2的前j個字符，所以dp[i][j] = 1 + dp[i-1][j]。 - 刪除
word2[j-1]字符，然后將word1的前i個字符轉(zhuǎn)換為word2的前j-1個字符，所以dp[i][j] = 1 + dp[i][j-1]。綜上所述，我們可以得到狀態(tài)轉(zhuǎn)移方程：
if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]) - 刪除
最后，我們可以通過填充dp數(shù)組來計算所需的最小步數(shù)。最終的結(jié)果即為dp[len(word1)][len(word2)]。文章來源地址http://www.zghlxwxcb.cn/news/detail-609058.html
def minDistance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n+1) for _ in range(m+1)] # 初始化dp數(shù)組
# 初始化邊界情況
for i in range(m+1):
dp[i][0] = i
for j in range(n+1):
dp[0][j] = j
# 計算dp數(shù)組
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])
return dp[m][n]
到了這里，關(guān)于每日一題之兩個字符串的刪除操作的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
