(Version 0.0)
这题是算法导论的书后习题，也是迄今为止LeetCode上面第二个我没想太长时间就直接放弃的题。第一个主动放弃的是Valid Number，那个题是因为嫌繁琐没什么太大意义，而这一个题则是感觉难度真的很大，如果之前没看过相关的东西的话自己做我觉得比AC Rate所体现的其实要难得多。
根据这个博客（http://www.cnblogs.com/TenosDoIt/p/3465316.html）里的说法，这一题的核心模型是：构建的二维数组中的元素dp[i][j]表示word1的前i个字符构成的substring和word2的前j个字符构成的substring所需要的min edit distance。若两个string中当前考虑的char是相同的，则dp[i][j] = dp[i - 1][j - 1]，因为从(i-1, j-1)匹配进化到(i, j)匹配不需要额外edit；若两个string中当前考虑的char不同，则有三种操作可以做：
1.insert，即给word1的当前subsring的结尾插入一个和word2当前substring结尾相同的char。此时应该去找的二维数组dp中的元素不太容易想清楚，应该是word1的前i - 1个char构成的substring和word2的前j个构成的substring的edit distance，因为我们要做的事情是确保word1的以i结尾的substring经过修改得到和word2的以j - 1结尾的substring相匹配，只有这样我们才能在word1尾巴上插入一个在word2中j位置的char后使得其依然匹配word2以j结尾。所以这个时候我们需要考虑的dp中的元素是dp[i][j - 1]。
2.delete，即删除word1的当前在i的char，这样我们需要考虑的东西很简单，就是word1的以i-1结尾的substring到word2以j结尾的substring的edit distance。所以这个时候我们要考虑的dp中的元素是dp[i - 1][j]。
3.replace，即把word1的当前在i的char替换成word2的当前在j的char，这时我们只需要保证word1的前i - 1个和word2的前j - 1个相匹配，所以要考虑的dp中的元素是dp[i - 1][j - 1]。
以上三个可能性中去最小的cost，然后再加1，即是我们当前考察的dp[i][j]要取的值。
这个模型建立好之后，代码倒是非常地简单：
1 public class Solution { 2 public int minDistance(String word1, String word2) { 3 int len1 = word1.length(); 4 int len2 = word2.length(); 5 int[][] dp = new int[len1 + 1][len2 + 1]; 6 for (int i = 0; i <= len1; i++) { 7 dp[i][0] = i; 8 } 9 for (int i = 0; i <= len2; i++) { 10 dp[0][i] = i; 11 } 12 for (int i = 1; i <= len1; i++) { 13 for (int j = 1; j <= len2; j++) { 14 if (word1.charAt(i - 1) == word2.charAt(j - 1)) { 15 dp[i][j] = dp[i - 1][j - 1]; 16 } else { 17 dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])); 18 } 19 } 20 } 21 return dp[len1][len2]; 22 } 23 }
跋：根据code ganker在自己的博客里写的，这题在面试时做时间还是太紧了，不过他在面Google的时候碰到过变形题，是问判断word1和word2的edit distance是不是1，想想怎么做？