这道题求一个字符串编辑成为还有一个字符串的最少操作数，操作包含加入，删除或者替换一个字符。这道题难度是比較大的，用常规思路出来的方法一般都是brute force，并且还不一定正确。
这事实上是一道二维动态规划的题目。模型上确实不easy看出来。以下我们来说说递推式。
我们维护的变量res[i][j]表示的是word1的前i个字符和word2的前j个字符编辑的最少操作数是多少。如果我们拥有res[i][j]前的全部历史信息，看看怎样在常量时间内得到当前的res[i][j]，我们讨论两种情况：
1）假设word1[i-1]=word2[j-1]，也就是当前两个字符同样，也就是不须要编辑。那么非常easy得到res[i][j]=res[i-1][j-1]，由于新增加的字符不用编辑。
2）假设word1[i-1]!=word2[j-1]。那么我们就考虑三种操作，假设是插入word1，那么res[i][j]=res[i-1][j]+1，也就是取word1前i-1个字符和word2前j个字符的最好结果。然后加入一个插入操作；假设是插入word2，那么res[i][j]=res[i][j-1]+1，道理同上面一种操作。假设是替换操作。那么类似于上面第一种情况，可是要加一个替换操作（由于word1[i-1]和word2[j-1]不相等），所以递推式是res[i][j]=res[i-1][j-1]+1。
上面列举的情况包括了全部可能性。有朋友可能会说为什么没有删除操作，事实上这里加入一个插入操作永远能得到与一个删除操作同样的效果。所以删除不会使最少操作数变得更好，因此假设我们是正向考虑。则不须要删除操作。取上面几种情况最小的操作数，即为另外一种情况的结果。即res[i][j] = min(res[i-1][j], res[i][j-1], res[i-1][j-1])+1。
接下来就是分析复杂度，算法时间上就是两层循环，所以时间复杂度是O(m*n)，空间上每一行仅仅须要上一行信息，所以能够仅仅用一维数组就可以，我们取m, n中小的放入内层循环。则复杂度是O(min(m,n))。
代码例如以下：
public int minDistance(String word1, String word2) {
if(word1.length()==0)
return word2.length();
if(word2.length()==0)
return word1.length();
String minWord = word1.length()>word2.length()?word2:word1;
String maxWord = word1.length()>word2.length()?word1:word2;
int[] res = new int[minWord.length()+1];
for(int i=0;i<=minWord.length();i++)
{
res[i] = i;
}
for(int i=0;i<maxWord.length();i++)
{
int[] newRes = new int[minWord.length()+1];
newRes[0] = i+1;
for(int j=0;j<minWord.length();j++)
{
if(minWord.charAt(j)==maxWord.charAt(i))
{
newRes[j+1]=res[j];
}
else
{
newRes[j+1] = Math.min(res[j],Math.min(res[j+1],newRes[j]))+1;
}
}
res = newRes;
}
return res[minWord.length()];
}
上面代码用了minWord,
maxWord是为了使得空间是min(m,n)。细节做得比較细，面试的时候可能不用刻意这么做。提一下就好。这道题目算是难度比較大的题目，所以在短时间的面试可能时间太紧了，所以也有变体。我自己在面试Google的时候，问的是怎样推断edit distance是不是在1以内，返回true或false就能够了。这样一改事实上就没有必要动态规划了，仅仅须要利用距离仅仅有1这一点进行推断就能够。大概思路就是仅仅要有一个不同，接下来就你不能有不同的，有兴趣的朋友可以考虑哈。
版权声明：本文博主原创文章，博客，未经同意不得转载。