title: Wagner Fischer algorithm + display steps
body: <p>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?</p>
  
  <p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
  <div class="snippet-code">
  <pre class="snippet-code-html lang-html prettyprint-override"><code>kitten -&gt; sitting
  1.replace k with s
  2.keep i
  3.keep t
  4.keep t
  5.replace t
  6.add g</code></pre>
  </div>
  </div>
  </p>
  
  <p>I tried to make function for display steps and can't figure out how to solve it.</p>
  
  <pre><code>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 &gt; InsCost + DelCost)
              ReplCost = InsCost + DelCost;
  
          Solution[][] ManageSol = new Solution[str1.length()+1][str2.length()+1];
  
          for(int i = 0; i &lt;= str1.length(); i++)
          {
              for(int j = 0; j &lt;= 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 &lt;= str1.length(); i++)
          {
              for (int j = 0; j &lt;= 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 &lt;= str1.length(); i++)
          {
              for (int j = 0; j &lt;= 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 &gt;= y)
              return x;
          return y;
      }
  
      static Solution minimum(int Ins, int Del, int Replace)
      {
  
          Solution solution = null;
          if(Ins &lt;= Del &amp;&amp; Ins &lt;= Replace)
          {
              solution = new Solution();
              solution.operation = 1;
              solution.solution = Ins;
              return solution;
          }
          else if(Del &lt;= Ins &amp;&amp; Del &lt;= 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 -&gt; %s", str1.charAt(i-1), str2.charAt(j-1));
              if(i &gt; 1 &amp;&amp; j &gt; 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 &gt; 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 &gt; 1)
                  path(ManagerSol, i-1,j, str1, str2);
          }
      }
  }
  </code></pre>
  
  <p>Output for kitten to sitting:</p>
  
  <p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
  <div class="snippet-code">
  <pre class="snippet-code-html lang-html prettyprint-override"><code>[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) </code></pre>
  </div>
  </div>
  </p>