給定兩個單詞 word1 和 word2，計算出將 word1 轉換成 word2 所使用的最少操作數(shù) 可以對一個單詞進行如下三種操作：
- 插入一個字符
- 刪除一個字符
- 替換一個字符
舉例說明：
輸入: word1 = "horse", word2 = "ros"
輸出: 3
解釋:
horse -> rorse (將 'h' 替換為 'r')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')
解釋：動態(tài)規(guī)劃法dp[i][j]表示 word1的前i個字符與word2的前j個字符之間的編輯距離，則當i||j==0時绘雁， dp[i][j] = 0+max(i,j).這一點很好理解橡疼。
一般情況：
如果word1[i-1][j-1] = = word 2[i-1][j-1] 時，則有：
- dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1]+1,dp[i-1][j]+1));
如果word1[i-1][j-1] 庐舟！= word 2[i-1][j-1]時欣除，則有：
- dp[i][j] = dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
for(int i=0; i<dp.size();i++){
for(int j=0;j<dp[0].size();j++){
if(i==0||j==0) dp[i][j] = i+j;
else if(word1[i-1]==word2[j-1]){
dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1]+1,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[word1.size()][word2.size()];
}
};
