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()];
}
};