algorithm
Editar distancia del algoritmo dinámico
Buscar..
Ediciones mínimas requeridas para convertir la cadena 1 a la cadena 2
La declaración del problema es como si nos dieran dos cadenas str1 y str2, entonces, ¿cuántos números mínimos de operaciones se pueden realizar en el str1 que se convierte en str2.Las operaciones pueden ser:
- Insertar
- retirar
- Reemplazar
Por ejemplo
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
Para resolver este problema usaremos una matriz 2D dp [n + 1] [m + 1] donde n es la longitud de la primera cadena y m es la longitud de la segunda cadena. Para nuestro ejemplo, si str1 es azcef y str2 es abcdef , nuestra matriz será dp [6] [7] y nuestra respuesta final se almacenará en 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 | | | | | | |
+---+---+---+---+---+---+---+
Para dp [1] [1] tenemos que comprobar lo que podemos hacer para convertir una en una .Es sera 0 .Para dp [1] [2] tenemos que comprobar qué podemos hacer para convertir una en ab .Es será 1 porque tenemos que insertar b . Entonces, después de la primera iteración, nuestra matriz se verá como
(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 | | | | | | |
+---+---+---+---+---+---+---+
Para iteración 2
Para dp [2] [1] tenemos que verificar que para convertir az a a debemos eliminar z , por lo tanto, dp [2] [1] será 1. Al igual que para dp [2] [2] necesitamos reemplazar z con b , por lo tanto, dp [2] [2] será 1. Por lo tanto, después de la segunda iteración, nuestra matriz dp [] se verá así.
(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 | | | | | | |
+---+---+---+---+---+---+---+
Entonces nuestra fórmula se verá como
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])
Después de la última iteración, nuestra matriz dp [] se verá como
(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 |
+---+---+---+---+---+---+---+
Implementación 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()];
}
Complejidad del tiempo
O(n^2)