作者:
idiont (supertroller)
2023-02-26 14:52:2072. Edit Distance
給你兩個字串 word1 跟 word2,
有三種操作可以做: 插入一個字元、刪除一個字元、修改一個字元,
求最少需要幾次操作才可以把 word1 變成 word2。
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (把 h 改成 r)
rorse -> rose (刪除 r)
rose -> ros (刪除 e)
Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (刪除 t)
inention -> enention (把 i 改成 e)
enention -> exention (把 n 改成 x)
exention -> exection (把 n 改成 c)
exection -> execution (插入 u)
解題思路:
Edit Distance 是蠻著名的 Dynamic Programming 題目,
可以用類似 LCS (Longest Commom Subsequence) 的方式去求。
我們用 word1[1~n] 來表示 word1 的元素,word2[1~m] 來表示 word2 的元素,
dp[i][j] 代表 word1[0~i] 最少要花幾步才能變 word2[0~j] (0 代表空字串),
轉移式:
dp[0][j] = j (空字串變成長度為 j 的字串需要花 j 步)
dp[i][0] = i (長度為 i 的字串需要花 i 步才能變空字串)
dp[i][j] = dp[i-1][j-1], if word1[i] = word2[j]
前面花 dp[i-1][j-1] 就能變成一樣的,最後多的字元一樣不需要再額外改變
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, if word1[i]≠word2[j]
第一個情況是把 word1[i] 刪除變成 word[0~i-1],用 dp[i-1][j] 步變成 word2,
第二個情況是花 dp[i][j-1] 步把 word1[0~i] 變成 word2[0~j-1],最後再插入字元,
第三個情況是把最後一個字元改成一樣的,剩下就是前面 dp[i-1][j-1] 的答案。
最後答案是 dp[n][m],就能把 word[1~n] 變成 word2[1~m]。
C++ code:
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() +
1));
for(int i = 1; i <= word2.size(); i++) dp[0][i] = i;
for(int i = 1; i <= word1.size(); i++) dp[i][0] = i;
for(int i = 1; i <= word1.size(); i++){
for(int j = 1; j <= word2.size(); j++){
if(word1[i-1] == word2[j-1]){ // 實際上是 0-indexed, 需要 -1
dp[i][j] = dp[i-1][j-1];
}
else{
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1);
}
}
}
return dp[word1.size()][word2.size()];
}
};