72.距離の編集

2001 ワード

タイトル


       word1   word2，    word1     word2            (        )。

                ：

a)       
b)       
c)

構想
ダイナミックプランニングのテーマ

再帰

dp[i][j]：  word1[1..i]    word2[1..j]       
d("abbc","acc") = d("abb","ac") 
                = 1 + min(d("ab","a"),  //   
                         d("abb","a"),  //  
                         d("ab",“ac”))     //

上記の再帰プロセス:

文字列の最後の1つが等しい場合、2つの文字列-1

等しくなければ:2.1置換操作:d(2文字列-1)を求める最小距離2.2追加操作:追加前の状態は、d(現在の文字列編集がパターン列-1となる)2.3削除操作:削除前の状態は、d(現在の文字列削除後にパターン列となる)

2の各操作+1

動的計画繰返し:d(i,j)はstr 1の前のi文字をstr 2の前のj文字に編集するために必要な最小edit distance

 d(2, 1)     = 1 + d(1, 1)

を表す.
edit("ab", "a") = 1 + edit("a", "a")

    d(1, 2)     = 1 + d(1, 1)

edit("a", "ab") = 1 + edit("a", "a")

    d(2, 2)     = 1 + d(1, 1)

edit("ab", "ac") = 1 + edit("a", "a")
コード#コード#

    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        //init
        //str2 == ""
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        //str1 == "" 
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //  、  、  
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i-1][j],dp[i][j-1])) + 1;
                }
            }
        }
        return dp[m][n];
    }

23個のサンプルで一貫したこと

python追記(4)