algorithm
Bewerk dynamisch afstandsalgoritme

Minimale bewerkingen vereist om string 1 naar string 2 te converteren

De probleemstelling is als wanneer we twee tekenreeksen str1 en str2 krijgen, hoeveel minimumaantal bewerkingen kunnen worden uitgevoerd op de str1 die wordt geconverteerd naar str2. De bewerkingen kunnen zijn:

1. invoegen
2. Verwijderen
3. Vervangen

Bijvoorbeeld

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

Om dit probleem op te lossen, gebruiken we een 2D-array dp [n + 1] [m + 1] waarbij n de lengte van de eerste string is en m de lengte van de tweede string is. Voor ons voorbeeld, als str1 azcef en str2 ABCDEF dan ons aanbod zal dp [6] [7] en onze eindantwoord u zich dp [5] worden opgeslagen [6].

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

Voor dp [1] [1] moeten we controleren wat we kunnen doen om een in een te converteren. Het zal 0 zijn . Voor dp [1] [2] moeten we controleren wat we kunnen doen om een te converteren naar ab . Het is 1 omdat we b moeten invoegen . Dus na de eerste iteratie ziet onze array eruit

          (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 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+ 

Voor iteratie 2

Voor dp [2] [1] moeten we controleren dat om az te converteren naar a, we z moeten verwijderen, dus dp [2] [1] zal 1 zijn. Simpelweg voor dp [2] [2] moeten we z vervangen met b , daarom zal dp [2] [2] 1 zijn . Dus na de 2e iteratie ziet onze dp [] array eruit.

         (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 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

Dus onze formule zal er uitzien

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])

Na de laatste iteratie ziet onze dp [] array eruit

          (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 |
     +---+---+---+---+---+---+---+

Implementatie in 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()];
}

Tijd Complexiteit

O(n^2)