https://leetcode.com/problems/edit-distance/description/
参考 CodeGanker:
我们维护的变量res[i][j]表示的是word1的前i个字符和word2的前j个字符编辑的最少操作数是多少。假设我们拥有res[i][j]前的所有历史信息，看看如何在常量时间内得到当前的res[i][j]，我们讨论两种情况：
1）如果word1[i-1]=word2[j-1]，也就是当前两个字符相同，也就是不需要编辑，那么很容易得到res[i][j]=res[i-1][j-1]，因为新加入的字符不用编辑；
2）如果word1[i-1]!=word2[j-1]，那么我们就考虑三种操作:
2.1) 如果是删除word1[i - 1]，那么res[i][j]=res[i-1][j]+1，也就是取word1前i-1个字符和word2前j个字符的最好结果，然后一个删除操作；
2.2) 如果是删除word2[j - 1]，那么res[i][j]=res[i][j-1]+1，道理同上面一种操作；
2.3) 如果是替换操作，那么类似于上面第一种情况，但是要加一个替换操作（因为word1[i-1]和word2[j-1]不相等），所以递推式是res[i][j]=res[i-1][j-1]+1。
上面列举的情况包含了所有可能性。
两点思考：
- 删除和插入操作对应的操作数是一样的；
"" => "abc" 进行插入操作同“abc” => ""进行删除操作，所需的操作数是一致的； - 删除操作应该是更容易维护和进行推导运算的。因为删除 word[index] 处的 char，继续向下进行 word[greaterThanIndex] 的 chars 可以继续进行；相反，对word index 处插入新的char，会使原来的 char 后移，word 位数增加，该 char 仍须继续被计算；
class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null || word1.length() == 0) {
return (word2 == null) ? 0 : word2.length();
}
if (word2 == null || word2.length() == 0) {
return (word1 == null) ? 0 : word1.length();
}
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= len2; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= len1; i++) {
char c1 = word1.charAt(i - 1);
for (int j = 1; j <= len2; j++) {
char c2 = word2.charAt(j - 1);
if (c1 == c2) {
dp[i][j] = dp[i - 1][j - 1];
} else {
int replace = dp[i - 1][j - 1] + 1; // replace c1 to c2 in word1
int delete = dp[i - 1][j] + 1; // delete c1 in word1 at (i - 1)
int insert = dp[i][j - 1] + 1; // delete c2 in word2 at (j - 1)
dp[i][j] = Math.min(Math.min(replace, delete), insert);
}
}
}
return dp[len1][len2];
}
}
From 九章：
Edit Distance
state: f[i][j]a的前i个字符“配上”b的前j个字符 最少要用几次编辑使得他们相等
function:
f[i][j] = MIN(f[i-1][j-1], f[i-1][j]+1, f[i][j-1]+1) // a[i] == b [j]
= MIN(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1 // a[i] != b[j] intialize: f[i][0] = i, f[0][j] = j
answer: f[a.length()][b.length()]
