Transformación de Cadenas

Este algoritmo responde a la pregunta de cuántas transformaciones unitarias se deben hacer para convertir una cadena de caracteres en otra. Las transformaciones unitarias pueden ser de tres tipos: insertar, eliminar o reemplazar un caracter.

El algoritmo a implementar es conocido como la Distancia de Levenshtein, el cual implementa una solución por programación dinámica en la cual, con la ayuda de una matriz que tiene tantas filas como la cantidad de caracteres de una cadena más uno, y tantas columnas como la cantidad de caracteres de la otra cadena más uno, se calcula el número de transformaciones que se deben hacer para  transformar los N prefijos de la primera cadena en los M prefijos de la segunda cadena.

public class ProblemaDistanciaCadenas {
    String cadena1;
    String cadena2;
    int[][] distancia;

    ProblemaDistanciaCadenas(String c1, String c2) {
        cadena1=c1;
        cadena2=c2;
        distancia=new int[cadena1.length()+1][cadena2.length()+1];
    }

    public void mostrarMatriz() {
        System.out.print("      ");
        for(int i=0; i<cadena2.length(); i++) System.out.printf("%6s", cadena2.charAt(i));
        System.out.println();
        for(int i=0; i<distancia.length; i++) {
            if(i==0) System.out.print("  ");
            else System.out.printf("%2s", cadena1.charAt(i-1));
            for(int j=0; j<distancia[i].length; j++) {
                System.out.printf("%,4d  ", distancia[i][j]);
            }
            System.out.println();
        }
    }

    private int minimo(int... v) {
        int menor = Integer.MAX_VALUE;
        for(int x: v) if(x<menor) menor=x;
        return menor;
    }

    private void calcularDistancias() {
        char[] cad1 = cadena1.toCharArray();
        char[] cad2 = cadena2.toCharArray();
        for(int i=0; i<=cad1.length; i++) distancia[i][0]=i;
        for(int j=0; j<=cad2.length; j++) distancia[0][j]=j;
        for(int i=1; i<=cad1.length; i++) {
            for(int j=1; j<=cad2.length; j++) {
                int cambio=0;
                if(cad1[i-1]!=cad2[j-1]) cambio=1;
                distancia[i][j] = minimo(distancia[i-1][j]+1,           // borrar
                                         distancia[i][j-1]+1,           // insertar
                                         distancia[i-1][j-1]+cambio);   // cambiar
            }
        }
    }

    public int getDistancia() {
        int respuesta = distancia[distancia.length-1][distancia[0].length-1];
        return respuesta;

    }

    public static void main(String [] args) {
        ProblemaDistanciaCadenas pdc = new ProblemaDistanciaCadenas("Hola", "Colas");
        pdc.calcularDistancias();
        pdc.mostrarMatriz();
        System.out.println(pdc.getDistancia());
    }
}

La complejidad del algoritmo es cuadrática, o más exactamente, O(NxM), donde N es el tamaño de la primera cadena y M el de la segunda.