编辑距离

题目：

给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。
你总共三种操作方法：
插入一个字符
删除一个字符
替换一个字符

上面的这个题目就是编辑距离问题，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。有些字符串相似算法就是基于编辑距离算法，距离越小，越相似。
可以用动态规划的思想去解决这个问题。

解析：

首先定义一个二维数组edit。edit的元素edit(i, j)表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串（包含第一个元素）的编辑距离。

显然可以有如下动态规划公式：

if i == 0 且 j == 0，edit(i, j) = 0
if i == 0 且 j > 0，edit(i, j) = j
if i > 0 且j == 0，edit(i, j) = i
if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。

上面的动态规划公式不难理解：
若两个字符串长度都为0，那么两个字符串相等，edit(i, j) = 0。
若两个字符串s1，s2。s1长度为0，s2长度为L，只要把s2的元素依次添加到s1，那么就有s1==s2，所以进行了L次插入操作。
若s1，s2长度分别为i，j都不为0，那么edit(i, j)为edit(i-1, j) +1，edit(i, j-1) + 1， edit(i-1, j-1) + f(i, j) }中的最小值。这三个包含了edit(i, j)所有的取值可能。

例子:

有word1 = "0failing", word2 = "0sailn"
下面展示在计算编辑距离过程中二维数组edit的元素变化。

Paste_Image.png Paste_Image.png Paste_Image.png Paste_Image.png

代码:

public static int minDistance(String word1, String word2) {
    // write your code here
    
    int[][] ptr = new int[word1.length()+1][word2.length()+1];
    
    for (int i = 0; i < word1.length()+1; i++) {
        ptr[i][0] = i;
    }
    for (int i = 1; i < word2.length()+1; i++) {
        ptr[0][i] = i;
    }
    
    for (int i = 1; i < word1.length()+1; i++) {
        for (int j = 1; j < word2.length()+1; j++) {
            
            int d = word1.charAt(i-1) == word2.charAt(j-1) ? 0 : 1;
            int temp = Math.min(ptr[i-1][j] + 1, ptr[i][j-1] + 1);
            ptr[i][j] = Math.min(temp, ptr[i-1][j-1] + d);
            
        }
    }
    
    return ptr[word1.length()][word2.length()];
    
}