題目給定兩個字串 word1 、 word2，並給定三種操作方式
- Insert a character
- Delete a character
- Replace a character
要我們求將 word1 透過這三種操作轉變為 word2 所需要的最少操作次數。
EX:
word1 = "horse", word2 = "ros"
Ans: 3.
step1: horse -> rorse (將 h 替換為 r )
step2: rose -> (刪除第二個 r )
step3: ros -> (刪除 e )
想法:
這題是一道 DP 的題目，我們可以一個二維陣列 dp 來表示所需的操作次數，其中 dp[i][j] 表示從 word[0:i-1] 轉變為 word[0:j-1] 所需的最少操作數(word1長度為 i 時轉變為 word2 長度為 j 時)，由於本題允許三種操作可以分析 dp 公式如下:
dp[i][j] = min dp[i -1][j -1] + 1 replace operation or 0 operation if word[i -1] == word[j -1]
dp[i -1][j] + 1 delete operation
dp[i][j -1] + 1 insert operation
例如: hors (i) 要轉換為 ros (j) 則如果我們知道怎摸從 hor (i-1) 轉換為 ro (j-1) 則我們就只需要將 hor -> ro 之後再替換掉最後一個數字即可，因此 dp[i][j] 會等於 dp[i-1][j-1] 的操作數再 +1， 或是直接等於 dp[i-1][j-1]，如果第 i 個 字元剛好和第 j 個字元一樣的話。
第二，我們也可以想成如果我們知道怎摸從 hor (i -1) 轉換為 ros (j) 的話，我們就只需要將 hor -> ros之後再刪掉 s 就可以完成轉換，因此 dp[i][j] 也可以是 dp[i -1][j] 的操作數再 + 1 次 delete operation，最後也可以想成如果我們知道怎摸從 hors (i) 轉換為 ro (j-1) 的話，我們就只需要將 hors -> ro 之後再插入 s 就可以完成轉換，因此 dp[i][j] 也可以是 dp[i][j -1] 的操作數再 + 1 次 insert operation. 最後因為題目要求 "最少" 操作數，因此取這三種情況的最小值。
Complexity: O(l1*l2) time, O(l1*l2) space. l1 is length of word1, l2 is length of word2.
完整程式碼:
解法一 (recursive) :
class Solution {
public:
int editDistance(const string& word1, const string& word2, int l1, int l2) {
if (l1 == 0) { return l2; }
if (l2 == 0) { return l1; }
if (dp[l1][l2] >= 0) { return dp[l1][l2]; }
int res;
if (word1[l1 - 1] == word2[l2 - 1]) {
res = editDistance(word1, word2, l1 - 1, l2 - 1);
}
else {
res = min(editDistance(word1, word2, l1 - 1, l2 - 1),
min(editDistance(word1, word2, l1, l2 - 1),
editDistance(word1, word2, l1 - 1, l2))) + 1;
}
return dp[l1][l2] = res;
}
int minDistance(string word1, string word2) {
// dp[i][j] means that min Distance from word1[0:i-1] to word2[0:j-1]
// i, j in dp means len of word1 and word2, respectively.
dp = vector<vector<int>>(word1.size() + 1, vector<int>(word2.size() + 1, -1));
return editDistance(word1, word2, word1.size(), word2.size());
}
private:
vector<vector<int>> dp;
};
解法二 (iterative) :
class Solution {
public:
int minDistance(string word1, string word2) {
int l1 = word1.size();
int l2 = word2.size();
// dp[i][j] means that min Distance from word1[0:i-1] to word2[0:j-1]
// i, j in dp means len of word1 and word2, respectively.
vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1));
// min distance from word1[0:i-1] to len "0" word2 is len of word1[0:i-1] which is i
for (int i = 0; i <= l1; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= l2; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= l1; i++) {
for (int j = 1; j <= l2; j++) {
// if last element is the same, then dp[i][j] is same as dp[i-1][j-1], otherwise need one more Replace operation
int t = (word1[i - 1] == word2[j - 1])? 0 : 1;
// dp[i][j] = min of dp[i-1][j-1] + 1 replace operation
// dp[i-1][j] + 1 delete operation
// dp[i][j-1] + 1 Insert operation
dp[i][j] = min(dp[i - 1][j - 1] + t, min(dp[i - 1][j], dp[i][j - 1]) + 1);
}
}
return dp[l1][l2];
}
};
沒有留言:
張貼留言