題目鏈接
tag:
- Easy;
- Dynamic Programming;
question
??Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
- Insert a character;
- Delete a character;
- Replace a character;
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2.
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
思路：
??這道題讓求從一個字符串轉(zhuǎn)變到另一個字符串需要的變換步驟樊卓，共有三種變換方式，插入一個字符杠河，刪除一個字符碌尔，和替換一個字符。根據(jù)以往的經(jīng)驗券敌，對于字符串相關(guān)的題目十有八九都是用動態(tài)規(guī)劃Dynamic Programming來解七扰，這道題也不例外。這道題我們需要維護(hù)一個二維的數(shù)組dp陪白，其中dp[i][j]表示從word1的前i個字符轉(zhuǎn)換到word2的前j個字符所需要的步驟颈走。那我們可以先給這個二維數(shù)組dp的第一行第一列賦值，這個很簡單咱士，因為第一行和第一列對應(yīng)的總有一個字符串是空串立由，于是轉(zhuǎn)換步驟完全是另一個字符串的長度。跟以往的DP題目類似序厉，難點還是在于找出遞推式锐膜，我們可以舉個例子來看，比如word1是“bbc"弛房，word2是”abcd“道盏，那么我們可以得到dp數(shù)組如下：
? a b c d
? 0 1 2 3 4
b 1 1 1 2 3
b 2 2 1 2 3
c 3 3 2 1 2
我們通過觀察可以發(fā)現(xiàn)，當(dāng)word1[i] == word2[j]時文捶，dp[i][j] = dp[i - 1][j - 1]荷逞，其他情況時，dp[i][j]是其左粹排，左上种远，上的三個值中的最小值加1，那么可以得到遞推式為：
if word1[i-1] == word2[j-1]:
??dp[i][j] = dp[i-1][j-1]
esle:
??min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1
代碼如下：
class Solution {
public:
int minDistance(string word1, string word2) {
int n1 = word1.size(), n2 = word2.size();
int dp[n1+1][n2+2];
for (int i=0; i<=n1; ++i)
dp[i][0] = i;
for (int i=0; i<=n2; ++i)
dp[0][i] = i;
for (int i=1; i<=n1; ++i) {
for (int j=1; j<=n2; ++j) {
if (word1[i-1] == word2[j-1])
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
}
}
return dp[n1][n2];
}
};
