Edit Distance 编辑距离(Hard)

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

解题思路

复杂度

时间 O(NM) 空间 O(NM)

这是算法导论中经典的一道动态规划的题。假设dp[i-1][j-1]表示一个长为i-1的字符串str1变为长为j-1的字符串str2的最短距离，如果我们此时想要把str1a这个字符串变成str2b这个字符串，我们有如下几种选择：

1. 替换： 在str1变成str2的步骤后，我们将str1a中的a替换为b，就得到str2b (如果a和b相等，就不用操作)
2. 增加： 在str1a变成str2的步骤后，我们再在末尾添加一个b，就得到str2b (str1a先根据已知距离变成str2，再加个b)
3. 删除： 在str1变成str2b的步骤后，对于str1a，我们将末尾的a删去，就得到str2b (str1a将a删去得到str1，而str1到str2b的编辑距离已知)

 public int editDistance2(String str1, String str2) {
    int len1 = str1.length();
    int len2 = str2.length();

    int[][] distances = new int[len1+1][len2+1];

    for (int i = 0; i < len1 + 1; ++i)
        distances[i][0] = i;
    for (int j = 0; j < len2 + 1; ++j)
        distances[0][j] = j;

    //http://www.programcreek.com/2013/12/edit-distance-in-java/
    for (int i = 1; i < len1 + 1; ++i) {
        for (int j = 1; j < len2 + 1; ++j) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1))
                distances[i][j] = distances[i - 1][j - 1];
            else {
                int deletion = distances[i - 1][j] + 1;
                int insertion = distances[i][j - 1] + 1;
                int substitution = distances[i - 1][j - 1] + 1;
                distances[i][j] = Util.min(deletion, insertion, substitution);
            }
        }
    }

    return distances[len1][len2];
}

References

1 详解请看斯坦福课件