De Wiki:
En informática, la distancia de edición es una forma de cuantificar qué tan diferentes son dos cadenas (por ejemplo, palabras) entre sí contando el número mínimo de operaciones necesarias para transformar una cadena en la otra.
Hay tres operaciones permitidas en una palabra: reemplazar, eliminar, insertar. Por ejemplo, la distancia de edición entre «a» y «b» es 1, la distancia de edición entre «abc» y «def» es 3. Esta publicación analiza cómo calcular la distancia de edición usando programación dinámica.
Análisis clave
Deja dp[i][j] representa la distancia de edición entre dos cadenas con longitud I y j, es decir, palabra1[0,…,i-1] y word2[0,…,j-1].
Existe una relación entre dp[i][j] y dp[i-1][j-1]. Digamos que nos transformamos de una cadena a otra. La primera cuerda tiene longitud I y su último carácter es «x»; la segunda cuerda tiene longitud j y su último carácter es «y». El siguiente diagrama muestra la relación.
- si x == y, entonces dp[i][j] == dp[i-1][j-1]
- si x! = y, e insertamos y para la palabra1, entonces dp[i][j] = dp[i][j-1] + 1
- si x! = y, y eliminamos x para la palabra1, entonces dp[i][j] = dp[i-1][j] + 1
- si x! = y, y reemplazamos x con y para la palabra1, entonces dp[i][j] = dp[i-1][j-1] + 1
- Cuando x! = Y, dp[i][j] es el mínimo de las tres situaciones.
Condición inicial:
dp[i][0] = yo, dp[0][j] = j
Solución 1 de Java: iteración
Después del análisis anterior, el código es solo una representación del mismo.
public static int minDistance(String word1, String word2) { int len1 = word1.length(); int len2 = word2.length(); // len1+1, len2+1, because finally return dp[len1][len2] int[][] dp = new int[len1 + 1][len2 + 1]; for (int i = 0; i <= len1; i++) { dp[i][0] = i; } for (int j = 0; j <= len2; j++) { dp[0][j] = j; } //iterate though, and check last char for (int i = 0; i < len1; i++) { char c1 = word1.charAt(i); for (int j = 0; j < len2; j++) { char c2 = word2.charAt(j); //if last two chars equal if (c1 == c2) { //update dp value for +1 length dp[i + 1][j + 1] = dp[i][j]; } else { int replace = dp[i][j] + 1; int insert = dp[i][j + 1] + 1; int delete = dp[i + 1][j] + 1; int min = replace > insert ? insert : replace; min = delete > min ? min : delete; dp[i + 1][j + 1] = min; } } } return dp[len1][len2]; } |
En t[][] dp = nuevo int[len1 + 1][len2 + 1]; para (int i = 0; i <= len1; i ++) {dp[i][0] = yo; } para (int j = 0; j <= len2; j ++) {dp[0][j] = j; } // iterar sin embargo, y comprobar el último carácter para (int i = 0; i
Solución Java 2: recursividad
Podemos escribir la solución en recursividad.
public int minDistance(String word1, String word2) { int m=word1.length(); int n=word2.length(); int[][] mem = new int[m][n]; for(int[] arr: mem){ Arrays.fill(arr, -1); } return calDistance(word1, word2, mem, m-1, n-1); } private int calDistance(String word1, String word2, int[][] mem, int i, int j){ if(i<0){ return j+1; }else if(j<0){ return i+1; } if(mem[i][j]!=-1){ return mem[i][j]; } if(word1.charAt(i)==word2.charAt(j)){ mem[i][j]=calDistance(word1, word2, mem, i-1, j-1); }else{ int prevMin = Math.min(calDistance(word1, word2, mem, i, j-1), calDistance(word1, word2, mem, i-1, j)); prevMin = Math.min(prevMin, calDistance(word1, word2, mem, i-1, j-1)); mem[i][j]=1+prevMin; } return mem[i][j]; } |
