Wagner Fischer algorithm + display steps

Question

I made an implementation of Wagner Fischer algorithm in java with input cost, but I want to display all steps. I search but can't find any idea.After a long time I tried to keep each transformation in matrix alongside cost and to go through back to first solution then reverse it... is this a good idea, if it is, how should I set condition?

kitten -> sitting
1.replace k with s
2.keep i
3.keep t
4.keep t
5.replace t
6.add g

I tried to make function for display steps and can't figure out how to solve it.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Principal {
    static int c1, c2, c3;
    static String word1, word2;

    public  static void main(String[] args) throws FileNotFoundException {
        Scanner data_in = new Scanner(new File("data.in"));
        word1 = data_in.next();
        word2 = data_in.next();
        c1 = data_in.nextInt();
        c2 = data_in.nextInt();
        c3 = data_in.nextInt();

        System.out.printf("\nInsert: %s, Delete: %s, Replace: %s\n", c1, c2, c3);

        System.out.printf("\nLevenstheinDistance: %s", LevenshteinDistance(word1, word2, c1, c2, c3));
    }

    private static int LevenshteinDistance(String str1, String str2, int InsCost, int DelCost, int ReplCost)
    {
        if(word1.length() == 0)
            return InsCost*str1.length();
        if(word2.length() == 0)
            return DelCost*str2.length();

        int substitutionCost = ReplCost;
        if(ReplCost > InsCost + DelCost)
            ReplCost = InsCost + DelCost;

        Solution[][] ManageSol = new Solution[str1.length()+1][str2.length()+1];

        for(int i = 0; i <= str1.length(); i++)
        {
            for(int j = 0; j <= str2.length(); j++){
                ManageSol[i][j] = new Solution();
            }
        }

        System.out.printf("\nLungime str1: %s", str1.length());
        System.out.printf("\nLungime str2: %s", str2.length());

        for(int i = 0; i <= str1.length(); i++)
        {
            for (int j = 0; j <= str2.length(); j++)
            {
                if (i == 0)
                    ManageSol[i][j].solution = j;
                else if (j == 0)
                    ManageSol[i][j].solution = i;
                else if (str1.charAt(i - 1) == str2.charAt(j - 1))
                {
                    substitutionCost = 0;
                    ManageSol[i][j].ecqualTo(minimum(
                            ManageSol[i][j - 1].solution + InsCost,
                            ManageSol[i - 1][j].solution + DelCost,
                            ManageSol[i - 1][j - 1].solution + substitutionCost));
                    System.out.printf("\nManagerSol[%s, %s]: ch1: %s, ch2: %s", i, j, str1.charAt(i - 1), str2.charAt(j - 1));
                }
                else
                {
                    substitutionCost = 1;
                    ManageSol[i][j].ecqualTo(minimum(
                            ManageSol[i][j - 1].solution + InsCost,
                            ManageSol[i - 1][j].solution + DelCost,
                            ManageSol[i - 1][j - 1].solution + substitutionCost));
                    System.out.printf("\nManagerSol[%s, %s]: ch1: %s, ch2: %s", i, j, str1.charAt(i - 1), str2.charAt(j - 1));
                }
            }
        }

        System.out.printf("\n");
        path(ManageSol, str1.length(), str2.length(), str1, str2);
        System.out.printf("\n");

        for(int i = 0; i <= str1.length(); i++)
        {
            for (int j = 0; j <= str2.length(); j++)
            {
                System.out.printf("[%s,%s]:(%s,%s) ", i, j, ManageSol[i][j].solution, ManageSol[i][j].operation);
            }
            System.out.printf("\n");
        }

        return ManageSol[str1.length()][str2.length()].solution;
    }

    static int minimum(int x, int y)
    {
        if(x >= y)
            return x;
        return y;
    }

    static Solution minimum(int Ins, int Del, int Replace)
    {

        Solution solution = null;
        if(Ins <= Del && Ins <= Replace)
        {
            solution = new Solution();
            solution.operation = 1;
            solution.solution = Ins;
            return solution;
        }
        else if(Del <= Ins && Del <= Replace)
        {
            solution = new Solution();
            solution.operation = 2;
            solution.solution = Del;
            return solution;
        }
        else
        {
            solution = new Solution();
            solution.solution = Replace;
            solution.operation = 0;
            return solution;
        }
    }

    //my failure, function that should display steps
    static void path(Solution[][] ManagerSol, int i, int j, String str1, String str2)
    {
        if(ManagerSol[i][j].operation == 0)
        {
            System.out.printf("\nReplace %s -> %s", str1.charAt(i-1), str2.charAt(j-1));
            if(i > 1 && j > 1)
                path(ManagerSol, i-1,j-1, str1, str2);
        }
        if(ManagerSol[i][j].operation == 1)
        {
            System.out.printf("\nAdd %s on position %s", str2.charAt(j-1), i-1);
            if(j > 1)
                path(ManagerSol, i,j-1, str1, str2);
        }
        if(ManagerSol[i][j].operation == 2)
        {
            System.out.printf("\nDelete %s", str1.charAt(i-1));
            if(j > 1)
                path(ManagerSol, i-1,j, str1, str2);
        }
    }
}

Output for kitten to sitting:

[0,0]:(0,3) [0,1]:(1,3) [0,2]:(2,3) [0,3]:(3,3) [0,4]:(4,3) [0,5]:(5,3) [0,6]:(6,3) [0,7]:(7,3) 
[1,0]:(1,3) [1,1]:(1,0) [1,2]:(2,1) [1,3]:(3,1) [1,4]:(4,1) [1,5]:(5,1) [1,6]:(6,1) [1,7]:(7,1) 
[2,0]:(2,3) [2,1]:(2,2) [2,2]:(1,0) [2,3]:(2,1) [2,4]:(3,1) [2,5]:(4,1) [2,6]:(5,1) [2,7]:(6,1) 
[3,0]:(3,3) [3,1]:(3,2) [3,2]:(2,2) [3,3]:(1,0) [3,4]:(2,1) [3,5]:(3,1) [3,6]:(4,1) [3,7]:(5,1) 
[4,0]:(4,3) [4,1]:(4,2) [4,2]:(3,2) [4,3]:(2,2) [4,4]:(1,0) [4,5]:(2,1) [4,6]:(3,1) [4,7]:(4,1) 
[5,0]:(5,3) [5,1]:(5,2) [5,2]:(4,2) [5,3]:(3,2) [5,4]:(2,2) [5,5]:(2,0) [5,6]:(3,1) [5,7]:(4,1) 
[6,0]:(6,3) [6,1]:(6,2) [6,2]:(5,2) [6,3]:(4,2) [6,4]:(3,2) [6,5]:(3,2) [6,6]:(2,0) [6,7]:(3,1) 

Answer 1

In general your idea is correct. It's even simpler than that. You don't need to store any additional information.

You can go backwards (starting from the end of the given strings) and use your dynamic programming values in the following way:

1. If one of the indices is 0, there is only one way to go.

2. Otherwise, you can look at 3 possible transitions "backwards" (from (i, j) to (i - 1, j - 1), (i - 1, j) and (i, j - 1)) and choose the one which yields the actual value for (i, j). If there are several possible options, you can choose any of them.

Once you know where to go from the given pair of positions, the operation is uniquely determined.

Answer 2

I'm not versed in Java but here is an illustration in JavaScript:

var a = 'kitten',
    b = 'sitting';

var m = new Array(a.length + 1);

for (var i=0; i<m.length; i++){
  m[i] = new Array(b.length + 1);
  
  for (var j=0; j<m[i].length; j++){
    if (i === 0) m[i][j] = j;
    if (j === 0) m[i][j] = i;
  }
}

for (var i=1; i<=a.length; i++){
  for (var j=1; j<=b.length; j++){

    // no change needed
    if (a[i - 1] === b[j - 1]){
      m[i][j] = m[i - 1][j - 1];
  
    // choose deletion or insertion
    } else {
      m[i][j] = Math.min(m[i - 1][j], m[i][j - 1], m[i - 1][j - 1]) + 1;
    }
  }
}

console.log('a: ' + JSON.stringify(a));
console.log('b: ' + JSON.stringify(b));

var i = a.length,
    j = b.length,
    steps = '';
    
while (i !== 0 && j !== 0){
  if (a[i - 1] === b[j - 1]){
    steps = 'no change; ' + steps;
    i--;
    j--;
    
  } else if (m[i - 1][j] < m[i][j - 1]){
    steps = 'delete \'' + a[i - 1] + '\'; ' + steps;
    i--;
    
  } else if (m[i - 1][j] === m[i][j - 1]){
    steps = 'replace \'' + a[i - 1] + '\' with \'' + b[j - 1] + '\'; ' + steps;
    i--;
    j--;
    
  } else {
    steps = 'insert \'' + b[j - 1] + '\'; ' + steps;
    j--;
  }
}

if (i === 0 && j > 0){
  steps = 'insert first ' + j + ' elements from b; ' + steps;
  
} else if (j === 0 && i > 0){
  steps = 'delete first ' + i + ' elements from a; ' + steps;
}

console.log('\n' + steps[0].toUpperCase() + steps.substr(1));

console.log('\nMatrix:\n');

for (var i in m){
  console.log(JSON.stringify(m[i]));
}