Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Solution：

第一遍做的时候没弄懂应该怎么做，只是有个感觉应该是DP。

对于一个位置，它有四种可能的操作：

1.insert

2.delete

3.replace

4.nothing

将两个word按长度排序，用长度短的去构成长度长的。

所以这是一个二维DP。

解法仍然是二维DP，只不过转换方程有变化。

如果是求最长子串，方程是：

                    

dp[i][j] =  dp[i-1][j-1] +1  if (A[i] == B[j])

           or = max(dp[i][j-1], dp[i-1][j]);

初始条件： dp[0][j] = 0, dp[i][0] = 0

 

但对于编辑距离的话，当我们要计算d(i,j)时，即计算A(i)到B(j)之间的编辑距离，此时，设A(i)形式是somestr1c；B(i)形如somestr2d的话，

      将somestr1变成somestr2的编辑距离已知是d(i-1,j-1)

将somestr1c变成somestr2的编辑距离已知是d(i,j-1)
将somestr1变成somestr2d的编辑距离已知是d(i-1,j)
那么利用这三个变量，就可以递推出d(i,j)了：
如果c==d，显然编辑距离和d(i-1,j-1)是一样的
如果c!=d，情况稍微复杂一点，

1. 如果将c替换成d，编辑距离是somestr1变成somestr2的编辑距离 + 1，也就是d(i-1,j-1) + 1
2. 如果在c后面添加一个字d，编辑距离就应该是somestr1c变成somestr2的编辑距离 + 1，也就是d(i,j-1) + 1
3. 如果将c删除了，那就是要将somestr1编辑成somestr2d，距离就是d(i-1,j) + 1

那最后只需要看着三种谁最小，就采用对应的编辑方案了。

递推公式出来了：

 

dp[i][j] =  dp[i-1][j-1]   if (A[i] == B[j])

           or = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) +1;

      初始条件： dp[0][j] = j and dp[i][0] = i   

public class Solution {
    int[][] map = null;
    public int minDistance(String word1, String word2) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(word1 == null && word2 == null) return 0;
        else if(word1 == null || word1.length() == 0) return word2.length();
        else if(word2 == null || word2.length() == 0) return word1.length();
        
        map = new int[word1.length()+1][word2.length()+1];
        for(int i = 0; i < word1.length()+1; i ++){
            map[i][0] = i;
        }
        for(int j = 0; j < word2.length()+1; j ++){
            map[0][j] = j;
        }
        for(int i = 1; i < word1.length()+1; i ++){
            for(int j = 1; j < word2.length()+1; j ++){
                if(word1.charAt(i-1) == word2.charAt(j-1))
                    map[i][j] = map[i-1][j-1];
                else{
                    map[i][j] = Math.min(map[i-1][j] + 1, map[i][j-1] + 1);
                    map[i][j] = Math.min(map[i-1][j-1] + 1, map[i][j]);
                }
            }
        }
        return map[word1.length()][word2.length()];
    }
    
}