Edit Distance

Explicación

Empezamos inicializando un arreglo $\texttt{dp}$ , donde $\texttt{dp}[i][j]$ es el número mínimo de ediciones para convertir los primeros $i$ caracteres del primer string, que denotamos como $\texttt{str1}$ , en los primeros $j$ caracteres del segundo string, que denotamos como $\texttt{str2}$ . Los casos base del arreglo $\texttt{dp}$ ocurren cuando uno de los prefijos está vacío.

Esto significa que inicializamos el arreglo $\texttt{dp}$ de la siguiente forma. Inicializamos $\texttt{dp}[i][0],$ donde $i$ es la longitud del prefijo en $\texttt{str1}$ , como $i$ porque se necesitan como mínimo $i$ eliminaciones para convertir los primeros $i$ caracteres en los primeros $0$ caracteres de $\texttt{str2}$ (un string vacío). De forma similar, inicializamos $\texttt{dp}[0][j],$ donde $j$ es la longitud del prefijo en $\texttt{str2}$ , como $j$ porque se necesitan $j$ inserciones para convertir los primeros $0$ caracteres de $\texttt{str1}$ (también un string vacío) en los primeros $j$ caracteres de $\texttt{str2}$ .

Ahora que inicializamos nuestro arreglo $\texttt{dp}$ , podemos pasar a la transición de $\texttt{dp}[i][j]$ . Las opciones que tenemos son eliminar, insertar o reemplazar un carácter de $\texttt{str1}$ , o no hacer nada si los caracteres actuales ya son iguales.

Cuando eliminamos un carácter, convertimos $\texttt{str1}[:i-1]$ en $\texttt{str2}[:j]$ , y luego eliminamos $\texttt{str1}[i-1]$ . Por lo tanto, esto significa que, si la última operación es una eliminación, $\texttt{dp}[i][j]$ es igual a $\texttt{dp}[i - 1][j] + 1$ , donde el $1$ extra es el costo de la operación de eliminación.

Cuando insertamos un carácter, efectivamente convertimos $\texttt{str1}[:i]$ en $\texttt{str2}[:j-1]$ , y luego insertamos $\texttt{str2}[j-1]$ . Así, $\texttt{dp}[i][j]$ es igual a $\texttt{dp}[i][j-1] + 1$ , donde el $1$ extra es el costo de la operación de inserción.

Finalmente, cuando reemplazamos un carácter, esencialmente convertimos $\texttt{str1}[:i-1]$ en $\texttt{str2}[:j-1]$ , y luego manejamos el último carácter. Si $\texttt{str1}[i-1]$ y $\texttt{str2}[j-1]$ son distintos, entonces eso cuenta como una operación de reemplazo. Así, la operación de reemplazo se puede representar de forma compacta como

\texttt{dp}[i][j] = \texttt{dp}[i - 1][j - 1] + (\texttt{str1}[i - 1] \neq \texttt{str2}[j - 1]),

donde $\texttt{str1}[i - 1] \neq \texttt{str2}[j - 1]$ es solo $1$ cuando realmente necesitamos reemplazar la letra.

Combinando la transición de cada operación, el número mínimo de ediciones requeridas para convertir los primeros $i$ caracteres de $\texttt{str1}$ en los primeros $j$ caracteres de $\texttt{str2}$ es

\texttt{dp}[i][j] = \min(\texttt{dp}[i - 1][j] + 1,~\texttt{dp}[i][j-1] + 1,~\texttt{dp}[i - 1][j - 1] + (\texttt{str1}[i - 1] \neq \texttt{str2}[j - 1])).

Usando esta transición, como cada estado depende solo de la celda de arriba, la celda de la izquierda y la celda diagonal superior izquierda, llenamos la tabla de arriba hacia abajo y de izquierda a derecha. Nuestra respuesta final es $\texttt{dp}[n][m].$

Implementación

Complejidad temporal: $\mathcal{O}(NM)$

JavaC++Python


import java.io.*;
import java.util.*;
 
public class EditDistance {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		char[] str1 = io.next().toCharArray();
		char[] str2 = io.next().toCharArray();
 
		/*
		 * dp[i][j] es el número mínimo de movimientos para cambiar las primeras i letras
		 * del string en las primeras j letras del resultado.
		 */
		int[][] dp = new int[str1.length + 1][str2.length + 1];
		for (int i = 0; i < dp.length; i++) { Arrays.fill(dp[i], Integer.MAX_VALUE); }
		dp[0][0] = 0;
		for (int i = 0; i <= str1.length; i++) {
			for (int j = 0; j <= str2.length; j++) {
				if (i != 0) {
					// Eliminar la letra i - 1 del string.
					dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
				}
				if (j != 0) {
					// Agregar la letra j - 1 del resultado al string.
					dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
				}
 
				// Hacer que la letra i - 1 sea igual a la letra j - 1 del resultado.
				if (i != 0 && j != 0) {
					int newCost =
					    dp[i - 1][j - 1] + ((str1[i - 1] == str2[j - 1]) ? 0 : 1);
					dp[i][j] = Math.min(dp[i][j], newCost);
				}
			}
		}
		io.println(dp[str1.length][str2.length]);
		io.close();
	}
	// CodeSnip{Kattio}
}


#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	std::string str1;
	std::string str2;
	std::cin >> str1 >> str2;
	/*
	 * dp[i][j] es el número mínimo de movimientos para cambiar las primeras i letras
	 * del string en las primeras j letras del resultado.
	 */
	vector<vector<int>> dp(str1.size() + 1, vector<int>(str2.size() + 1, INT32_MAX));
	dp[0][0] = 0;
	for (int i = 0; i <= str1.size(); i++) {
		for (int j = 0; j <= str2.size(); j++) {
			if (i != 0) {
				// Eliminar la letra i - 1 del string.
				dp[i][j] = std::min(dp[i][j], dp[i - 1][j] + 1);
			}
			if (j != 0) {
				// Agregar la letra j - 1 del resultado al string.
				dp[i][j] = std::min(dp[i][j], dp[i][j - 1] + 1);
			}
 
			// Hacer que la letra i - 1 sea igual a la letra j - 1 del resultado.
			if (i != 0 && j != 0) {
				int new_cost = dp[i - 1][j - 1] + (str1[i - 1] != str2[j - 1]);
				dp[i][j] = std::min(dp[i][j], new_cost);
			}
		}
	}
	cout << dp[str1.size()][str2.size()] << endl;
}


str1 = input()
str2 = input()
 
"""
dp[i][j] es el número mínimo de movimientos para cambiar las primeras i letras
del string en las primeras j letras del resultado.
"""
dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
 
# se necesitan i ediciones para convertir los primeros i caracteres del string 1 en el string vacío
for i in range(len(str1) + 1):
	dp[i][0] = i
# se necesitan j ediciones para convertir el string vacío en los primeros j caracteres del string 2
for j in range(len(str2) + 1):
	dp[0][j] = j
 
for i in range(1, len(str1) + 1):
	for j in range(1, len(str2) + 1):
		"""
		eliminar la letra i - 1 del string,
		agregar la letra j - 1 del resultado al string,
		o hacer que la letra i - 1 sea igual a la letra j - 1 del resultado.
		"""
		dp[i][j] = min(
			dp[i - 1][j] + 1,
			dp[i][j - 1] + 1,
			dp[i - 1][j - 1] + (str1[i - 1] != str2[j - 1]),
		)
 
print(dp[len(str1)][len(str2)])