algorithm
距離の動的アルゴリズムの編集

文字列1を文字列2に変換するために必要な最小限の編集

問題文は、str1とstr2という2つの文字列が与えられ、次にstr1に実行できる操作の最小数がstr2に変換されるようなものです。操作は次のようになります。

1. インサート
2. 削除する
3. 置換

例えば

Input: str1 = "geek", str2 = "gesek"
Output: 1
We only need to insert s in first string

Input: str1 = "march", str2 = "cart"
Output: 3
We need to replace m with c and remove character c and then replace h with t

この問題を解決するために、2D配列dp [n + 1] [m + 1]を使用します（nは最初の文字列の長さ、mは2番目の文字列の長さです）。この例では、str1がazcefでstr2がabcdefの場合、配列はdp [6] [7]になり、最終的な答えはdp [5] [6]に格納されます。

          (a) (b) (c) (d) (e) (f)
     +---+---+---+---+---+---+---+
     | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
     +---+---+---+---+---+---+---+
  (a)| 1 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (z)| 2 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (c)| 3 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (e)| 4 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (f)| 5 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

DPの場合は[1] [1]我々は0 .FOR DPとなります.ITに変換するために何ができるかを確認する必要があります[1] [2]我々は、AB .ITに変換するために何ができるかを確認する必要があり私たちは。だからbを挿入する必要があるため、当社の配列は次のようになります第一反復の後に1になります

          (a) (b) (c) (d) (e) (f)
     +---+---+---+---+---+---+---+
     | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
     +---+---+---+---+---+---+---+
  (a)| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
  (z)| 2 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (c)| 3 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (e)| 4 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (f)| 5 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+ 

繰り返し2の場合

DPの場合は[2] [1]我々は、したがって、DP、我々はZを削除する必要にAZを変換することを確認する必要があり[2] [1] DPのために1 .Similaryになります[2] [2]我々は、zを交換する必要がありますBで、それ故にDP [2] [2]第2回反復した後、私たちのDP []配列は次のようになります。だから1になります。

         (a) (b) (c) (d) (e) (f)
     +---+---+---+---+---+---+---+
     | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
     +---+---+---+---+---+---+---+
  (a)| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
  (z)| 2 | 1 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
  (c)| 3 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (e)| 4 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (f)| 5 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

だから私たちの公式は次のようになります

if characters are same
    dp[i][j] = dp[i-1][j-1];
else
    dp[i][j] = 1 + Min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

最後の反復の後、私たちのdp []配列は次のようになります

          (a) (b) (c) (d) (e) (f)
     +---+---+---+---+---+---+---+
     | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
     +---+---+---+---+---+---+---+
  (a)| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
  (z)| 2 | 1 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
  (c)| 3 | 2 | 2 | 1 | 2 | 3 | 4 |
     +---+---+---+---+---+---+---+
  (e)| 4 | 3 | 3 | 2 | 2 | 2 | 3 |
     +---+---+---+---+---+---+---+
  (f)| 5 | 4 | 4 | 2 | 3 | 3 | 3 |
     +---+---+---+---+---+---+---+

Javaでの実装

public int getMinConversions(String str1, String str2){
    int dp[][] = new int[str1.length()+1][str2.length()+1];
    for(int i=0;i<=str1.length();i++){
        for(int j=0;j<=str2.length();j++){
            if(i==0)
                dp[i][j] = j;
            else if(j==0)
                dp[i][j] = i;
            else if(str1.charAt(i-1) == str2.charAt(j-1))
                dp[i][j] = dp[i-1][j-1];
            else{
                dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
            }
        }
    }
    return dp[str1.length()][str2.length()];
}

時間の複雑さ

O(n^2)