Transformacion de Cadenas - El camino a seguir

En el siguiente programa se complementa la clase ProblemaDistanciaCadenas para agregar un método que recorre la matriz de distancias para encontrar el camino de transformaciones que lleva de una cadena a la otra. Este método, que recibe el nombre de getCamino, recorre hacia atrás la matriz, mirando los elementos adyacentes que sean menores o que el elemento actual.

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 void getCamino() {
        int i=distancia.length-1;
        int j=distancia[0].length-1;
        String[] ruta = new String[Math.max(cadena1.length(), cadena2.length())+1];
        int k=ruta.length;
         while(i+j>0) {
            if(i>0 && distancia[i-1][j]  < distancia[i][j]) {
                ruta[--k] = "Elimina '" + cadena1.charAt(--i)+"'";
            }
            else if(j>0 && distancia[i][j-1]  < distancia[i][j]) {
                ruta[--k] = "Inserta '" + cadena2.charAt(--j)+"'";
            }
            else if(i > 0 && j > 0 && distancia[i - 1][j - 1] < distancia[i][j]) {
                ruta[--k] = "Reemplaza '" + cadena1.charAt(--i) + "' por '" + cadena2.charAt(--j) + "'";
                continue;
            }
            else if(i > 0 && j > 0 && distancia[i - 1][j - 1] == distancia[i][j]) {
                ruta[--k] = "Avanza sin cambios";
                i--;
                j--;
            }
        }
       for(String x: ruta) System.out.println(x);
    }

    public static void main(String [] args) {
        ProblemaDistanciaCadenas pdc = new ProblemaDistanciaCadenas("algoritmos", "logaritmo");
        pdc.calcularDistancias();
        pdc.getCamino();
    }
}

La complejidad continúa siendo cuadrática pues la nueva función agregada solo recorre tantos elementos como filas o columnas tenga la matriz y no toda la matriz.