Posted on 2023-02-26 20:10
Uriel 閱讀(52)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
給出兩個單詞word1和word2，有三種操作，改變一個字母，增加or刪除一個字母，問至少幾次操作可以讓word1變為word2
DP
轉移方程：
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
1 #72
2 #Runtime: 114 ms (Beats 65.95%)
3 #Memory: 16.9 MB (Beats 42.38%)
4
5 class Solution(object):
6 def minDistance(self, word1, word2):
7 """
8 :type word1: str
9 :type word2: str
10 :rtype: int
11 """
12 m = len(word1)
13 n = len(word2)
14 dp = [[0] * (n + 1) for _ in range(m + 1)]
15 for i in range(1, m + 1):
16 dp[i][0] = i
17 for j in range(1, n + 1):
18 dp[0][j] = j
19 for i in range(1, m + 1):
20 for j in range(1, n + 1):
21 if word1[i - 1] == word2[j - 1]:
22 dp[i][j] = dp[i - 1][j - 1]
23 else:
24 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
25 return dp[m][n]