美文网首页动态规划
2 Sequences DP - 72. Edit Distan

2 Sequences DP - 72. Edit Distan

作者: Super_Alan | 来源:发表于2018-04-12 03:50 被阅读9次

    https://leetcode.com/problems/edit-distance/description/

    参考 CodeGanker:

    我们维护的变量res[i][j]表示的是word1的前i个字符和word2的前j个字符编辑的最少操作数是多少。假设我们拥有res[i][j]前的所有历史信息,看看如何在常量时间内得到当前的res[i][j],我们讨论两种情况:
    1)如果word1[i-1]=word2[j-1],也就是当前两个字符相同,也就是不需要编辑,那么很容易得到res[i][j]=res[i-1][j-1],因为新加入的字符不用编辑;
    2)如果word1[i-1]!=word2[j-1],那么我们就考虑三种操作:
    2.1) 如果是删除word1[i - 1],那么res[i][j]=res[i-1][j]+1,也就是取word1前i-1个字符和word2前j个字符的最好结果,然后一个删除操作;
    2.2) 如果是删除word2[j - 1],那么res[i][j]=res[i][j-1]+1,道理同上面一种操作;
    2.3) 如果是替换操作,那么类似于上面第一种情况,但是要加一个替换操作(因为word1[i-1]和word2[j-1]不相等),所以递推式是res[i][j]=res[i-1][j-1]+1。

    上面列举的情况包含了所有可能性。

    两点思考:

    • 删除和插入操作对应的操作数是一样的;"" => "abc" 进行插入操作“abc” => "" 进行删除操作,所需的操作数是一致的;
    • 删除操作应该是更容易维护和进行推导运算的。因为删除 word[index] 处的 char,继续向下进行 word[greaterThanIndex] 的 chars 可以继续进行;相反,对word index 处插入新的char,会使原来的 char 后移,word 位数增加,该 char 仍须继续被计算;
    class Solution {
        public int minDistance(String word1, String word2) {
            if (word1 == null || word1.length() == 0) {
                return (word2 == null) ? 0 : word2.length();
            }
            if (word2 == null || word2.length() == 0) {
                return (word1 == null) ? 0 : word1.length();
            }
            
            int len1 = word1.length();
            int len2 = word2.length();
            int[][] dp = new int[len1 + 1][len2 + 1];
            
            for (int i = 0; i <= len1; i++) {
                dp[i][0] = i;
            }
            for (int j = 0; j <= len2; j++) {
                dp[0][j] = j;
            }
            
            for (int i = 1; i <= len1; i++) {
                char c1 = word1.charAt(i - 1);
                for (int j = 1; j <= len2; j++) {
                    char c2 = word2.charAt(j - 1);
                    if (c1 == c2) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        int replace = dp[i - 1][j - 1] + 1; // replace c1 to c2 in word1
                        int delete = dp[i - 1][j] + 1;      // delete c1 in word1 at (i - 1)
                        int insert = dp[i][j - 1] + 1;      // delete c2 in word2 at (j - 1)
                        dp[i][j] = Math.min(Math.min(replace, delete), insert);
                    }
                }
            }
            return dp[len1][len2];
        }
    }
    

    From 九章:

    Edit Distance
    state: f[i][j]a的前i个字符“配上”b的前j个字符 最少要用几次编辑使得他们相等
    function:
    f[i][j] = MIN(f[i-1][j-1], f[i-1][j]+1, f[i][j-1]+1) // a[i] == b [j]
    = MIN(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1 // a[i] != b[j] intialize: f[i][0] = i, f[0][j] = j
    answer: f[a.length()][b.length()]

    相关文章

      网友评论

        本文标题:2 Sequences DP - 72. Edit Distan

        本文链接:https://www.haomeiwen.com/subject/yhuhhftx.html