Re: [閒聊] 每日LeetCode已回收
72. 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()];
}
};
---
這個經典題難度竟然是 Hard
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1677394342.A.D95.html
→
02/26 14:55,
2年前
, 1F
02/26 14:55, 1F
※ 編輯: idiont (140.113.229.216 臺灣), 02/26/2023 16:29:58
→
02/26 21:13,
2年前
, 2F
02/26 21:13, 2F
討論串 (同標題文章)
完整討論串 (本文為第 251 之 719 篇)：