algorithm
Modifier l'algorithme dynamique de distance

Modifications minimales requises pour convertir la chaîne 1 en chaîne 2

L'énoncé du problème est comme si on nous donnait deux chaînes str1 et str2, puis combien de nombres minimum d'opérations peuvent être effectuées sur la str1 qu'elle convertit en str2. Les opérations peuvent être:

1. Insérer
2. Retirer
3. Remplacer

Par exemple

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

Pour résoudre ce problème, nous utiliserons un tableau 2D dp [n + 1] [m + 1] où n est la longueur de la première chaîne et m la longueur de la deuxième chaîne. Pour notre exemple, si str1 est azcef et str2 est abcdef, notre tableau sera dp [6] [7] et notre réponse finale sera stockée dans 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 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

Pour dp [1] [1] , nous devons vérifier que pouvons - nous faire pour convertir un en sera de 0 .Il dp .Pour [1] [2] , nous devons vérifier que pouvons - nous faire pour convertir un en ab .It sera 1 parce que nous devons insérer b . Donc, après la 1ère itération, notre tableau ressemblera à

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

Pour itération 2

Pour dp [2] [1] , nous devons vérifier que convertir az à nous devons supprimer z, d' où dp [2] [1] sera 1 .Similary pour dp [2] [2] nous devons remplacer z avec b , donc dp [2] [2] sera 1. Après la 2ème itération, notre tableau dp [] ressemblera.

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

Donc, notre formule ressemblera à

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

Après la dernière itération, notre tableau dp [] ressemblera à

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

Implémentation en 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()];
}

La complexité du temps

O(n^2)