Étant donné deux chaînes str1 et str2 et les opérations ci-dessous pouvant être effectuées sur str1. Trouver le nombre minimum de modifications (opérations) requises pour convertir 'str1' en 'str2'.
- Insérer
- Retirer
- Remplacer
Toutes les opérations ci-dessus sont de coût égal.
Exemples:
Entrée : str1 = "geek", str2 = "geek" Sortie : 1 Nous pouvons convertir str1 en str2 en insérant un 's'. Entrée : str1 = "chat", str2 = "couper" Sortie : 1 Nous pouvons convertir str1 en str2 en remplaçant 'a' par 'u'. Entrée : str1 = "dimanche", str2 = "samedi" Sortie : 3 Les trois derniers et les premiers caractères sont identiques. Nous fondamentalement besoin de convertir "un" en "atur". Cela peut être fait en utilisant ci-dessous trois opérations. Remplacez 'n' par 'r', insérez t, insérez a
Quels sont les sous-problèmes dans ce cas ?
L'idée est de traiter tous les caractères un par un en partant du côté gauche ou droit des deux chaînes.
Traversons depuis le coin droit, il y a deux possibilités pour chaque paire de caractères traversés.
m : longueur de str1 (première chaîne) n : longueur de str2 (deuxième chaîne)
- Si les derniers caractères de deux chaînes sont identiques, rien à faire. Ignorer les derniers caractères et obtenir le nombre de chaînes restantes. On revient donc pour les longueurs m-1 et n-1.
- Sinon (si les derniers caractères ne sont pas identiques), nous considérons toutes les opérations sur 'str1', considérons les trois opérations sur le dernier caractère de la première chaîne, calculons de manière récursive le coût minimum pour les trois opérations et prenons un minimum de trois valeurs.
- Insérer : Répéter pour m et n-1
- Supprimer : se reproduire pour m-1 et n
- Remplacer : se reproduire pour m-1 et n-1
Vous trouverez ci-dessous la mise en œuvre de la solution récursive naïve ci-dessus.
int editDist(string str1, string str2, int m, int n){ // If first string is empty, the only option is to // insert all characters of second string into first if (m == 0) return n; // If second string is empty, the only option is to // remove all characters of first string if (n == 0) return m; // If last characters of two strings are same, nothing // much to do. Ignore last characters and get count for // remaining strings. if (str1[m - 1] == str2[n - 1]) return editDist(str1, str2, m - 1, n - 1); // If last characters are not same, consider all three // operations on last character of first string, // recursively compute minimum cost for all three // operations and take minimum of three values. return 1 + min(editDist(str1, str2, m, n - 1), // Insert editDist(str1, str2, m - 1, n), // Remove editDist(str1, str2, m - 1, n - 1) // Replace );}// Driver codeint main(){ // your code goes here string str1 = "sunday"; string str2 = "saturday"; cout << editDist(str1, str2, str1.length(), str2.length()); return 0;}3
La complexité temporelle de la solution ci-dessus est exponentielle. Dans le pire des cas, nous pouvons finir par faire O(3^m ) opérations. Le pire des cas se produit lorsqu'aucun des caractères de deux chaînes ne correspond. Vous trouverez ci-dessous un diagramme d'appel récursif pour le pire des cas.
Nous pouvons voir que de nombreux sous-problèmes sont résolus, encore et encore, par exemple, eD(2, 2) est appelé trois fois. Puisque les mêmes sous-problèmes sont appelés à nouveau, ce problème a la propriété Overlapping Subproblems. Donc, le problème Edit Distance a les deux propriétés d'un problème de programmation dynamique. Comme d'autres problèmes typiques de programmation dynamique (DP), les recalculs des mêmes sous-problèmes peuvent être évités en construisant un tableau temporaire qui stocke les résultats des sous-problèmes.
int editDistDP(string str1, string str2, int m, int n){ // Create a table to store results of subproblems int dp[m + 1][n + 1]; // Fill d[][] in bottom up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { // If first string is empty, only option is to // insert all characters of second string if (i == 0) dp[i][j] = j; // Min. operations = j // If second string is empty, only option is to // remove all characters of second string else if (j == 0) dp[i][j] = i; // Min. operations = i // If last characters are same, ignore last char // and recur for remaining string else if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; // If the last character is different, consider // all possibilities and find the minimum else dp[i][j] = 1 + min(dp[i][j - 1], // Insert dp[i - 1][j], // Remove dp[i - 1][j - 1]); // Replace } } return dp[m][n];}// Driver codeint main(){ // your code goes here string str1 = "sunday"; string str2 = "saturday"; cout << editDistDP(str1, str2, str1.length(), str2.length()); return 0;}3
Complexité temporelle : O(mxn)
Espace auxiliaire : O(mxn)
Solution complexe spatiale : Dans la méthode ci-dessus, nous avons besoin d'un espace O(mxn). Cela ne conviendra pas si la longueur des chaînes est supérieure à 2000 car il ne peut créer qu'un tableau 2D de 2000 x 2000. Pour remplir une ligne dans le tableau DP, nous n'avons besoin que d'une seule ligne la ligne supérieure. Par exemple, si nous remplissons les i = 10 lignes dans le tableau DP, nous n'avons besoin que des valeurs de la 9ème ligne. Nous créons donc simplement un tableau DP de longueur 2 x str1. Cette approche réduit la complexité spatiale. Voici l'implémentation C++ du problème mentionné ci-dessus
void EditDistDP(string str1, string str2){ int len1 = str1.length(); int len2 = str2.length(); // Create a DP array to memoize result // of previous computations int DP[2][len1 + 1]; // To fill the DP array with 0 memset(DP, 0, sizeof DP); // Base condition when second string // is empty then we remove all characters for (int i = 0; i <= len1; i++) DP[0][i] = i; // Start filling the DP // This loop run for every // character in second string for (int i = 1; i <= len2; i++) { // This loop compares the char from // second string with first string // characters for (int j = 0; j <= len1; j++) { // if first string is empty then // we have to perform add character // operation to get second string if (j == 0) DP[i % 2][j] = i; // if character from both string // is same then we do not perform any // operation . here i % 2 is for bound // the row number. else if (str1[j - 1] == str2[i - 1]) { DP[i % 2][j] = DP[(i - 1) % 2][j - 1]; } // if character from both string is // not same then we take the minimum // from three specified operation else { DP[i % 2][j] = 1 + min(DP[(i - 1) % 2][j], min(DP[i % 2][j - 1], DP[(i - 1) % 2][j - 1])); } } } // after complete fill the DP array // if the len2 is even then we end // up in the 0th row else we end up // in the 1th row so we take len2 % 2 // to get row cout << DP[len2 % 2][len1] << endl;}// Driver programint main(){ string str1 = "food"; string str2 = "money"; EditDistDP(str1, str2); return 0;}4
Complexité temporelle : O(mxn)
Espace auxiliaire : O( m )
Il s'agit d'une version mémorisée de la récursivité, c'est-à-dire Top-Down DP :
int minDis(string s1, string s2, int n, int m, vector<vector<int> >& dp){ // If any string is empty, // return the remaining characters of other string if (n == 0) return m; if (m == 0) return n; // To check if the recursive tree // for given n & m has already been executed if (dp[n][m] != -1) return dp[n][m]; // If characters are equal, execute // recursive function for n-1, m-1 if (s1[n - 1] == s2[m - 1]) { return dp[n][m] = minDis(s1, s2, n - 1, m - 1, dp); } // If characters are nt equal, we need to // find the minimum cost out of all 3 operations. // 1. insert 2.delete 3.replace else { int insert, del, replace; // temp variables insert = minDis(s1, s2, n, m - 1, dp); del = minDis(s1, s2, n - 1, m, dp); replace = minDis(s1, s2, n - 1, m - 1, dp); return dp[n][m] = 1 + min(insert, min(del, replace)); }}// Driver programint main(){ string str1 = "voldemort"; string str2 = "dumbledore"; int n = str1.length(), m = str2.length(); vector<vector<int> > dp(n + 1, vector<int>(m + 1, -1)); cout << minDis(str1, str2, n, m, dp); return 0; // This code is a contribution of Bhavneet Singh}Complexité temporelle : O(m*n)
Espace auxiliaire : O( m*n)+O(m+n)
(m*n) espace de tableau supplémentaire et (m+n) espace de pile récursif.