Editar distancia | DP-5 – Part 1

 

Dadas dos strings str1 y str2 y por debajo de las operaciones que se pueden realizar en str1. Encuentre el número mínimo de ediciones (operaciones) requeridas para convertir ‘str1’ en ‘str2’.  

  1. Insertar
  2. Remover
  3. Reemplazar

Todas las operaciones anteriores son de igual costo. 

Ejemplos: 

Input:   str1 = "geek", str2 = "gesek"
Output:  1
We can convert str1 into str2 by inserting a 's'.

Input:   str1 = "cat", str2 = "cut"
Output:  1
We can convert str1 into str2 by replacing 'a' with 'u'.

Input:   str1 = "sunday", str2 = "saturday"
Output:  3
Last three and first characters are same.  We basically
need to convert "un" to "atur".  This can be done using
below three operations. 
Replace 'n' with 'r', insert t, insert a

¿Cuáles son los subproblemas en este caso?  
La idea es procesar todos los caracteres uno por uno comenzando desde el lado izquierdo o derecho de ambas strings. 
Atravesemos desde la esquina derecha, hay dos posibilidades para cada par de caracteres atravesados.  

m: Length of str1 (first string)
n: Length of str2 (second string)
  1. Si los últimos caracteres de dos strings son iguales, no hay mucho que hacer. Ignore los últimos caracteres y cuente las strings restantes. Entonces recurrimos para las longitudes m-1 y n-1.
  2. De lo contrario (si los últimos caracteres no son los mismos), consideramos todas las operaciones en ‘str1’, consideramos las tres operaciones en el último carácter de la primera string, calculamos recursivamente el costo mínimo para las tres operaciones y tomamos un mínimo de tres valores. 
    1. Insertar: recurrencia para m y n-1
    2. Eliminar: recurrencia para m-1 y n
    3. Reemplazar: recurrencia para m-1 y n-1

A continuación se muestra la implementación de la solución recursiva Naive anterior.

C++

// A Naive recursive C++ program to find minimum number
// operations to convert str1 to str2
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to find minimum of three numbers
int min(int x, int y, int z) { return min(min(x, y), z); }
 
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 code
int main()
{
    // your code goes here
    string str1 = "sunday";
    string str2 = "saturday";
 
    cout << editDist(str1, str2, str1.length(),
                     str2.length());
 
    return 0;
}

Java

// A Naive recursive Java program to find minimum number
// operations to convert str1 to str2
class EDIST {
    static int min(int x, int y, int z)
    {
        if (x <= y && x <= z)
            return x;
        if (y <= x && y <= z)
            return y;
        else
            return z;
    }
 
    static 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.charAt(m - 1) == str2.charAt(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 Code
    public static void main(String args[])
    {
        String str1 = "sunday";
        String str2 = "saturday";
 
        System.out.println(editDist(
            str1, str2, str1.length(), str2.length()));
    }
}
/*This code is contributed by Rajat Mishra*/

Python3

# A Naive recursive Python program to find minimum number
# operations to convert str1 to str2
 
 
def editDistance(str1, str2, m, 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 editDistance(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(editDistance(str1, str2, m, n-1),    # Insert
                   editDistance(str1, str2, m-1, n),    # Remove
                   editDistance(str1, str2, m-1, n-1)    # Replace
                   )
 
 
# Driver code
str1 = "sunday"
str2 = "saturday"
print (editDistance(str1, str2, len(str1), len(str2)))
 
# This code is contributed by Bhavya Jain

C#

// A Naive recursive C# program to
// find minimum numberoperations
// to convert str1 to str2
using System;
 
class GFG {
    static int min(int x, int y, int z)
    {
        if (x <= y && x <= z)
            return x;
        if (y <= x && y <= z)
            return y;
        else
            return z;
    }
 
    static 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 code
    public static void Main()
    {
        String str1 = "sunday";
        String str2 = "saturday";
        Console.WriteLine(
            editDist(str1, str2, str1.Length, str2.Length));
    }
}
 
// This Code is Contributed by Sam007

PHP

<?php
// A Naive recursive Python program 
// to find minimum number operations
// to convert str1 to str2
function editDistance($str1, $str2,
                      $m, $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 editDistance($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(editDistance($str1, $str2,
                                $m, $n - 1), // Insert
                   editDistance($str1, $str2,
                                $m - 1, $n), // Remove
                   editDistance($str1, $str2,
                                $m - 1, $n - 1)); // Replace
}
 
// Driver Code
$str1 = "sunday";
$str2 = "saturday";
echo editDistance($str1, $str2, strlen($str1),
                                strlen($str2));
 
// This code is contributed
// by Shivi_Aggarwal
?>

Javascript

<script>
 
// Javascript program to
// find minimum numberoperations
// to convert str1 to str2
function min(x, y, z)
{
    if (x <= y && x <= z)
        return x;
    if (y <= x && y <= z)
        return y;
    else
        return z;
}
 
function editDist(str1, str2, m, 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 code
let str1 = "sunday";
let str2 = "saturday";
document.write(editDist(str1, str2, str1.length,
                                    str2.length));
 
// This code is contributed by target_2
 
</script>
Producción

3
Producción

3

La complejidad temporal de la solución anterior es exponencial. En el peor de los casos, podemos terminar haciendo operaciones O(3 m ). El peor de los casos ocurre cuando ninguno de los caracteres de dos strings coincide. A continuación se muestra un diagrama de llamadas recursivas para el peor de los casos. 

EditDistance

Podemos ver que muchos subproblemas se resuelven una y otra vez, por ejemplo, eD(2, 2) se llama tres veces. Dado que los mismos subproblemas se vuelven a llamar, este problema tiene la propiedad Superposición de subproblemas. Entonces, el problema Editar distancia tiene ambas propiedades (ver this y this ) de un problema de programación dinámica. Al igual que otros problemas típicos de programación dinámica (DP), los cálculos de los mismos subproblemas se pueden evitar mediante la construcción de una array temporal que almacena los resultados de los subproblemas.

C++

// A Dynamic Programming based C++ program to find minimum
// number operations to convert str1 to str2
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to find the minimum of three numbers
int min(int x, int y, int z) { return min(min(x, y), z); }
 
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 code
int main()
{
    // your code goes here
    string str1 = "sunday";
    string str2 = "saturday";
 
    cout << editDistDP(str1, str2, str1.length(),
                       str2.length());
 
    return 0;
}

Java

// A Dynamic Programming based Java program to find minimum
// number operations to convert str1 to str2
class EDIST {
    static int min(int x, int y, int z)
    {
        if (x <= y && x <= z)
            return x;
        if (y <= x && y <= z)
            return y;
        else
            return z;
    }
 
    static int editDistDP(String str1, String str2, int m,
                          int n)
    {
        // Create a table to store results of subproblems
        int dp[][] = new int[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.charAt(i - 1)
                         == str2.charAt(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 Code
    public static void main(String args[])
    {
        String str1 = "sunday";
        String str2 = "saturday";
        System.out.println(editDistDP(
            str1, str2, str1.length(), str2.length()));
    }
} /*This code is contributed by Rajat Mishra*/

Python3

# A Dynamic Programming based Python program for edit
# distance problem
 
 
def editDistDP(str1, str2, m, n):
    # Create a table to store results of subproblems
    dp = [[0 for x in range(n + 1)] for x in range(m + 1)]
 
    # Fill d[][] in bottom up manner
    for i in range(m + 1):
        for j in range(n + 1):
 
            # 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
            elif j == 0:
                dp[i][j] = i    # Min. operations = i
 
            # If last characters are same, ignore last char
            # and recur for remaining string
            elif str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]
 
            # If last character are different, consider all
            # possibilities and find 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 code
str1 = "sunday"
str2 = "saturday"
 
print(editDistDP(str1, str2, len(str1), len(str2)))
# This code is contributed by Bhavya Jain

C#

// A Dynamic Programming based
// C# program to find minimum
// number operations to
// convert str1 to str2
using System;
 
class GFG {
    static int min(int x, int y, int z)
    {
        if (x <= y && x <= z)
            return x;
        if (y <= x && y <= z)
            return y;
        else
            return z;
    }
 
    static int editDistDP(String str1, String str2, int m,
                          int n)
    {
        // Create a table to store
        // results of subproblems
        int[, ] dp = new int[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)
 
                    // Min. operations = j
                    dp[i, j] = j;
 
                // If second string is empty, only option is
                // to remove all characters of second string
                else if (j == 0)
 
                    // Min. operations = i
                    dp[i, j] = 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 code
    public static void Main()
    {
        String str1 = "sunday";
        String str2 = "saturday";
        Console.Write(editDistDP(str1, str2, str1.Length,
                                 str2.Length));
    }
}
// This Code is Contributed by Sam007

PHP

<?php
// A Dynamic Programming based
// Python program for edit
// distance problem
function editDistDP($str1, $str2,
                    $m, $n)
{
// Fill d[][] in bottom up manner
for ($i = 0; $i <= $m; $i++)
{ 
    for ($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 last character are different,
        // consider all possibilities and
        // find 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 Code
$str1 = "sunday";
$str2 = "saturday";
 
echo editDistDP($str1, $str2, strlen($str1),
                              strlen($str2));
 
// This code is contributed
// by Shivi_Aggarwal
?>

Javascript

<script>
 
// A Dynamic Programming based
// Javascript program to find minimum
// number operations to convert str1 to str2
 
function min(x,y,z)
{
    if (x <= y && x <= z)
            return x;
        if (y <= x && y <= z)
            return y;
        else
            return z;
}
 
function editDistDP(str1,str2,m,n)
{
    // Create a table to store results of subproblems
        let dp = new Array(m + 1);
        for(let i=0;i<m+1;i++)
        {
            dp[i]=new Array(n+1);
            for(let j=0;j<n+1;j++)
            {
                dp[i][j]=0;
            }
        }
  
        // Fill d[][] in bottom up manner
        for (let i = 0; i <= m; i++) {
            for (let 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 Code
let str1 = "sunday";
let str2 = "saturday";
document.write(editDistDP(
str1, str2, str1.length, str2.length));
 
// This code is contributed by unknown2108
 
</script>
Producción

3

Complejidad Temporal: O(mxn) 
Espacio Auxiliar: O(mxn)

Solución del complejo espacial : en el método anterior, requerimos el espacio O (mxn). Esto no será adecuado si la longitud de las strings es superior a 2000, ya que solo puede crear una array 2D de 2000 x 2000. Para llenar una fila en la array DP, solo necesitamos una fila, la fila superior. Por ejemplo, si estamos llenando i = 10 filas en la array DP, solo requerimos valores de la novena fila. Así que simplemente creamos una array DP de 2 x str1 de longitud. Este enfoque reduce la complejidad del espacio. Aquí está la implementación en C++ del problema mencionado anteriormente

C++

// A Space efficient Dynamic Programming
// based C++ program to find minimum
// number operations to convert str1 to str2
#include <bits/stdc++.h>
using namespace std;
 
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 program
int main()
{
    string str1 = "food";
    string str2 = "money";
    EditDistDP(str1, str2);
    return 0;
}

Java

// A Space efficient Dynamic Programming
// based Java program to find minimum
// number operations to convert str1 to str2
import java.util.*;
class GFG
{
 
static 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 = new int[2][len1 + 1];
 
 
    // 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.charAt(j - 1) == str2.charAt(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 + Math.min(DP[(i - 1) % 2][j],
                                       Math.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
    System.out.print(DP[len2 % 2][len1] +"\n");
}
 
// Driver program
public static void main(String[] args)
{
    String str1 = "food";
    String str2 = "money";
    EditDistDP(str1, str2);
}
}
 
// This code is contributed by aashish1995

Python3

# A Space efficient Dynamic Programming
# based Python3 program to find minimum
# number operations to convert str1 to str2
def EditDistDP(str1, str2):
     
    len1 = len(str1)
    len2 = len(str2)
 
    # Create a DP array to memoize result
    # of previous computations
    DP = [[0 for i in range(len1 + 1)]
             for j in range(2)];
 
    # Base condition when second String
    # is empty then we remove all characters
    for i in range(0, len1 + 1):
        DP[0][i] = i
 
    # Start filling the DP
    # This loop run for every
    # character in second String
    for i in range(1, len2 + 1):
         
        # This loop compares the char from
        # second String with first String
        # characters
        for j in range(0, len1 + 1):
 
            # 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.
            elif(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
    print(DP[len2 % 2][len1], "")
 
# Driver code
if __name__ == '__main__':
     
    str1 = "food"
    str2 = "money"
     
    EditDistDP(str1, str2)
 
# This code is contributed by gauravrajput1

C#

// A Space efficient Dynamic Programming
// based C# program to find minimum
// number operations to convert str1 to str2
using System;
class GFG
{
 
static 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 = new int[2, len1 + 1];
 
 
    // 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 + Math.Min(DP[(i - 1) % 2, j],
                                       Math.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
    Console.Write(DP[len2 % 2, len1] +"\n");
}
 
// Driver program
public static void Main(String[] args)
{
    String str1 = "food";
    String str2 = "money";
    EditDistDP(str1, str2);
}
}
 
// This code is contributed by aashish1995

Javascript

<script>
// A Space efficient Dynamic Programming
// based Javascript program to find minimum
// number operations to convert str1 to str2
function EditDistDP(str1, str2)
{
    let len1 = str1.length;
    let len2 = str2.length;
  
    // Create a DP array to memoize result
    // of previous computations
    let DP = new Array(2);
    for(let i = 0; i < 2; i++)
    {
        DP[i] = new Array(len1+1);
        for(let j = 0; j < len1 + 1; j++)
            DP[i][j] = 0;
    }
  
  
    // Base condition when second String
    // is empty then we remove all characters
    for (let i = 0; i <= len1; i++)
        DP[0][i] = i;
  
    // Start filling the DP
    // This loop run for every
    // character in second String
    for (let i = 1; i <= len2; i++)
    {
        
        // This loop compares the char from
        // second String with first String
        // characters
        for (let 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 + Math.min(DP[(i - 1) % 2][j],
                                       Math.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
    document.write(DP[len2 % 2][len1] +"<br>");
}
 
// Driver program
let str1 = "food";
let str2 = "money";
EditDistDP(str1, str2);
 
// This code is contributed by patel2127.
</script>
Producción

4

Complejidad Temporal: O(mxn) 
Espacio Auxiliar: O( m )

Esta es una versión memorizada de la recursividad, es decir, Top-Down DP:

C++14

#include <bits/stdc++.h>
using namespace std;
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 program
int 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
}

Java

import java.util.*;
class GFG {
 
    static int minDis(String s1, String s2, int n, int m,
                      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.charAt(n - 1) == s2.charAt(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.
        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 + Math.min(insert, Math.min(del, replace));
        }
    }
    // Driver program
    public static void main(String[] args)
    {
 
        String str1 = "voldemort";
        String str2 = "dumbledore";
 
        int n = str1.length(), m = str2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i < n + 1; i++)
            Arrays.fill(dp[i], -1);
        System.out.print(minDis(str1, str2, n, m, dp));
    }
}
 
// This code is contributed by gauravrajput1

Python3

def minDis(s1, s2, n, m, 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]) :          
    if(dp[n - 1][m - 1] == -1) :
        dp[n][m] = minDis(s1, s2, n - 1, m - 1, dp)
        return dp[n][m]                  
    else :
        dp[n][m] = dp[n - 1][m - 1]
        return dp[n][m]
         
  # If characters are nt equal, we need to          
  # find the minimum cost out of all 3 operations.        
  else :           
    if(dp[n - 1][m] != -1) :  
      m1 = dp[n - 1][m]     
    else :
      m1 = minDis(s1, s2, n - 1, m, dp)
              
    if(dp[n][m - 1] != -1) :               
      m2 = dp[n][m - 1]           
    else :
      m2 = minDis(s1, s2, n, m - 1, dp)  
    if(dp[n - 1][m - 1] != -1) :   
      m3 = dp[n - 1][m - 1]   
    else :
      m3 = minDis(s1, s2, n - 1, m - 1, dp)
     
    dp[n][m] = 1 + min(m1, min(m2, m3))
    return dp[n][m]
     
    # Driver code
str1 = "voldemort"
str2 = "dumbledore"
    
n = len(str1)
m = len(str2)
dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]
              
print(minDis(str1, str2, n, m, dp))
 
# This code is contributed by divyesh072019.

C#

using System;
using System.Collections.Generic;
class GFG {
 
  static int minDis(string s1, string s2, int n,
                    int m, List<List<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])
    {          
      if(dp[n - 1][m - 1] == -1)
      {              
        return dp[n][m] = minDis(s1, s2, n - 1, m - 1, dp);          
      }       
      else
        return dp[n][m] = dp[n - 1][m - 1];  
    }
 
 
    // If characters are nt equal, we need to
    // find the minimum cost out of all 3 operations.
    else
    {          
      int m1, m2, m3;        // temp variables  
 
      if(dp[n - 1][m] != -1)
      {   
        m1 = dp[n - 1][m];     
      }          
      else
      {  
        m1 = minDis(s1, s2, n - 1, m, dp);     
      }           
 
      if(dp[n][m - 1] != -1)
      {               
        m2 = dp[n][m - 1];           
      }           
      else
      {   
        m2 = minDis(s1, s2, n, m - 1, dp);     
      }                                  
 
      if(dp[n - 1][m - 1] != -1)
      {   
        m3 = dp[n - 1][m - 1];     
      }  
      else
      {  
        m3 = minDis(s1, s2, n - 1, m - 1, dp);      
      }    
      return dp[n][m] = 1+ Math.Min(m1, Math.Min(m2, m3));       
    }
 
  }
 
  // Driver code
  static void Main()
  {
    string str1 = "voldemort";
    string str2 = "dumbledore";
 
    int n = str1.Length, m = str2.Length;  
    List<List<int>> dp = new List<List<int>>();
    for(int i = 0; i < n + 1; i++)
    {
      dp.Add(new List<int>());
      for(int j = 0; j < m + 1; j++)
      {
        dp[i].Add(-1);
      }
    }
    Console.WriteLine(minDis(str1, str2, n, m, dp));
  }
}
 
// This code is contributed by divyeshrabadiya07.

Javascript

<script>
 
function minDis(s1,s2,n,m,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])
  {         
    if(dp[n - 1][m - 1] == -1)
    {             
      return dp[n][m] = minDis(s1, s2, n - 1, m - 1, dp);         
    }      
    else
      return dp[n][m] = dp[n - 1][m - 1]; 
  }
    
  // If characters are nt equal, we need to
            
  // find the minimum cost out of all 3 operations.    
  else
  {         
    let m1, m2, m3;        // temp variables 
    if(dp[n-1][m] != -1)
    {  
      m1 = dp[n - 1][m];    
    }         
    else
    { 
      m1 = minDis(s1, s2, n - 1, m, dp);    
    }          
              
    if(dp[n][m - 1] != -1)
    {              
      m2 = dp[n][m - 1];          
    }          
    else
    {  
      m2 = minDis(s1, s2, n, m - 1, dp);    
    }                                 
     
    if(dp[n - 1][m - 1] != -1)
    {  
      m3 = dp[n - 1][m - 1];    
    } 
    else
    { 
      m3 = minDis(s1, s2, n - 1, m - 1, dp);     
    }   
    return dp[n][m] = 1 + Math.min(m1, Math.min(m2, m3));      
  }
}
 
// Driver program
 
let str1 = "voldemort";
let str2 = "dumbledore";
 
let n= str1.length, m = str2.length;  
let dp = new Array(n + 1);
for(let i = 0; i < n + 1; i++)
{
    dp[i]=new Array(m+1);
    for(let j=0;j<m+1;j++)
        dp[i][j]=-1;
}
 
document.write(minDis(str1, str2, n, m, dp));
 
// This code is contributed by avanitrachhadiya2155
 
</script>
Producción

7

Complejidad Temporal: O(mxn) 
Espacio Auxiliar: O( m *n)+O(m+n)  

(m*n) espacio de array adicional y (m+n) espacio de pila recursivo.

Aplicaciones : hay muchas aplicaciones prácticas del algoritmo de distancia de edición, consulte la API de Lucene para obtener una muestra. Otro ejemplo, muestra todas las palabras en un diccionario que están muy cerca de una palabra dada escrita incorrectamente.

Gracias a Vivek Kumar por sugerir actualizaciones.
Gracias a Venki por proporcionar la publicación inicial. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *