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’.
- Insertar
- Remover
- Reemplazar
Todas las operaciones anteriores son de igual costo.
Ejemplos:
Entrada: str1 = “geek”, str2 = “gesek”
Salida: 1
Podemos convertir str1 en str2 insertando una ‘s’.Entrada: str1 = «gato», str2 = «cortar»
Salida: 1
Podemos convertir str1 en str2 reemplazando ‘a’ con ‘u’.Entrada: str1 = «domingo», str2 = «sábado»
Salida: 3 Los
últimos tres y los primeros caracteres son iguales. Básicamente
necesitamos convertir «un» a «atur». Esto se puede hacer usando
las siguientes tres operaciones.
Reemplace ‘n’ con ‘r’, inserte t, inserte 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. Recorramos desde la esquina derecha, hay dos posibilidades para cada par de caracteres que se recorren. Las siguientes son las condiciones:
- 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.
- De lo contrario (si los últimos caracteres no son iguales), 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.
- Insertar: recurrencia para m y n-1
- Eliminar: recurrencia para m-1 y n
- Reemplazar: recurrencia para m-1 y n-1
A continuación se muestra la implementación del enfoque 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 program
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
);
}
public static void main(String args[])
{
String str1 = "sunday";
String str2 = "saturday";
System.out.println(editDist(str1, str2, str1.length(), str2.length()));
}
}
Python
# 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 program to test the above function str1 = "sunday" str2 = "saturday" print editDistance(str1, str2, len(str1), len(str2))
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));
}
}
Javascript
<script>
// A Naive recursive Javascript
// program to find minimum number
// operations to convert str1 to str2
// Utility function to find minimum of three numbers
function min(x, y, z)
{
return Math.min(Math.min(x, y), 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 program
// your code goes here
var str1 = "sunday";
var str2 = "saturday";
document.write( editDist(str1, str2, str1.length, str2.length));
</script>
Producción:
3
La complejidad temporal de la solución anterior es O(3^n), que es exponencial. 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.
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. El enfoque de abajo hacia arriba se puede encontrar aquí .
El problema también se puede resolver usando Programación Dinámica de arriba hacia abajo y usando memorización. En el código recursivo, la memorización se puede utilizar para evitar problemas de superposición. Hay varias llamadas repetitivas que se pueden calcular en O(1) si el valor se almacena cuando se llama por primera vez. Al observar el código recursivo, se ve que un máximo de dos parámetros están cambiando su valor en cada llamada recursiva. Habrá casos en los que la misma llamada recursiva haya sido llamada anteriormente. Dado que dos parámetros no son constantes, se puede usar una array 2-D para evitar llamadas repetitivas. Por lo tanto, el valor devuelto se almacena en una array 2-D. A continuación se muestran los pasos:
- Inicialice una array DP 2-D de tamaño m * n con -1 en todo el índice.
- En cada llamada recursiva, almacene el valor devuelto en dp[m][n] de modo que si se vuelve a llamar a func(m, n) , se pueda responder en O(1) sin usar la recursividad.
- Compruebe si la llamada recursiva ha sido visitada anteriormente o no comprobando el valor en dp[m][n].
A continuación se muestra la implementación del enfoque anterior:
C++
// A memoization program to find minimum number
// operations to convert str1 to str2
#include <bits/stdc++.h>
using namespace std;
// Maximum 2-D array column size
const int maximum = 1000;
// 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, int dp[][maximum])
{
// 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 the recursive call has been
// called previously, then return
// the stored value that was calculated
// previously
if (dp[m - 1][n - 1] != -1)
return dp[m - 1][n - 1];
// If last characters of two strings are same, nothing
// much to do. Ignore last characters and get count for
// remaining strings.
// Store the returned value at dp[m-1][n-1]
// considering 1-based indexing
if (str1[m - 1] == str2[n - 1])
return dp[m - 1][n - 1] = editDist(str1, str2, m - 1, n - 1, dp);
// 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.
// Store the returned value at dp[m-1][n-1]
// considering 1-based indexing
return dp[m - 1][n - 1] = 1 + min(editDist(str1, str2, m, n - 1, dp), // Insert
editDist(str1, str2, m - 1, n, dp), // Remove
editDist(str1, str2, m - 1, n - 1, dp) // Replace
);
}
// Driver Code
int main()
{
string str1 = "sunday";
string str2 = "saturday";
int m = str1.length();
int n = str2.length();
// Declare a dp array which stores
// the answer to recursive calls
int dp[m][maximum];
// initially all index with -1
memset(dp, -1, sizeof dp);
// Function call
// memoization and top-down approach
cout << editDist(str1, str2, m, n, dp);
return 0;
}
Java
// A memoization program to find minimum number
// operations to convert str1 to str2
import java.util.*;
class GFG
{
// Maximum 2-D array column size
static int maximum = 1000;
// Utility function to find minimum of three numbers
static int min(int x, int y, int z)
{
return Math.min((Math.min(x, y)), z);
}
static int editDist(String str1, String str2, int m,
int n, int[][] dp)
{
// 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 the recursive call has been
// called previously, then return
// the stored value that was calculated
// previously
if (dp[m - 1][n - 1] != -1)
return dp[m - 1][n - 1];
// If last characters of two strings are same,
// nothing much to do. Ignore last characters and
// get count for remaining strings.
// Store the returned value at dp[m-1][n-1]
// considering 1-based indexing
if (str1.charAt(m - 1) == str2.charAt(n - 1))
return dp[m - 1][n - 1]
= editDist(str1, str2, m - 1, n - 1, dp);
// 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.
// Store the returned value at dp[m-1][n-1]
// considering 1-based indexing
return dp[m - 1][n - 1]
= 1
+ min(editDist(str1, str2, m, n - 1,
dp), // Insert
editDist(str1, str2, m - 1, n,
dp), // Remove
editDist(str1, str2, m - 1, n - 1,
dp) // Replace
);
}
// Driver code
public static void main(String[] args)
{
String str1 = "sunday";
String str2 = "saturday";
int m = str1.length();
int n = str2.length();
// Declare a dp array which stores
// the answer to recursive calls
int[][] dp = new int[m][maximum];
for (int i = 0; i < dp.length; i++)
Arrays.fill(dp[i], -1);
// Function call
// memoization and top-down approach
System.out.println(editDist(str1, str2, m, n, dp));
}
}
// This code is contributed by Karandeep Singh
Python3
# A memoization program to find minimum number
# operations to convert str1 to str2
def editDistance(str1, str2, m, n, d = {}):
key = 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 key in d:
return d[key]
# 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.
# Store the returned value at dp[m-1][n-1]
# considering 1-based indexing
d[key] = 1 + min(editDistance(str1, str2, m, n - 1), # Insert
editDistance(str1, str2, m - 1, n), # Remove
editDistance(str1, str2, m - 1, n - 1)) # Replace
return d[key]
# Driver code
str1 = "sunday"
str2 = "saturday"
print(editDistance(str1, str2, len(str1), len(str2)))
# This code is contributed by puranjanprithu
Javascript
<script>
// A memoization program to find minimum number
// operations to convert str1 to str2
// Maximum 2-D array column size
const maximum = 1000;
// Utility function to find minimum of three numbers
function min(x, y, z)
{
return Math.min(Math.min(x, y), z);
}
function editDist(str1, str2, m, n, dp)
{
// 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 the recursive call has been
// called previously, then return
// the stored value that was calculated
// previously
if (dp[m - 1][n - 1] != -1)
return dp[m - 1][n - 1];
// If last characters of two strings are same, nothing
// much to do. Ignore last characters and get count for
// remaining strings.
// Store the returned value at dp[m-1][n-1]
// considering 1-based indexing
if (str1[m - 1] == str2[n - 1])
return dp[m - 1][n - 1] = editDist(str1, str2, m - 1, n - 1, dp);
// 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.
// Store the returned value at dp[m-1][n-1]
// considering 1-based indexing
return dp[m - 1][n - 1] = 1 + min(editDist(str1, str2, m, n - 1, dp), // Insert
editDist(str1, str2, m - 1, n, dp), // Remove
editDist(str1, str2, m - 1, n - 1, dp) // Replace
);
}
// Driver Code
let str1 = "sunday";
let str2 = "saturday";
let m = str1.length;
let n = str2.length;
// Declare a dp array which stores
// the answer to recursive calls
// initially all index with -1
let dp = new Array(m);
for(let i = 0; i < m; i++){
dp[i] = new Array(maximum).fill(-1);
}
// Function call
// memoization and top-down approach
document.write(editDist(str1, str2, m, n, dp));
// This code is contributed by shinjanpatra
</script>
Producción:
3
Complejidad de tiempo : O(M * N)
Espacio auxiliar : O(M * N)