Finding Levenshtein distance on two string

Question

I am trying to implement in Eclipse Java Levenshtein distance on the following two strings:

I took the idea from Wikipedia, but I don't know why my output is wrong, I need help to find my mistake/s.

1. "kruskal"

2. "causal"

    package il.ac.oranim.alg2016;
     public class OPT {
    public static void main(String[] args)
   {
   
   char[] t={'k','r','u','s','k','a','l'};
   char[] s={'c','a','u','s','a','l'};
   for (int i=0;i<=s.length;i++)
   {
       for (int j=0;j<=t.length;j++)
       System.out.print(LevenshteinDistance(s,t)[i][j]+" ");
       System.out.println();
   }
    }
   private static int[][] LevenshteinDistance(char s[], char t[])
    {
      // d is a table with m+1 rows and n+1 columns
       int[][] d=new int[s.length+1][t.length+1];    
      for (int i=0;i<=s.length;i++)
        d[i][0] = i; // deletion
      for (int j=0;j<=t.length;j++)
        d[0][j] = j; // insertion
   
      for (int j=1;j<t.length;j++)
      {
        for (int i=1;i<s.length;i++)
        {
          if (s[i] ==t[j]) 
            d[i][j]=d[i-1][j-1];
          else
            d[i][j] = Math.min(Math.min((d[i-1][ j] + 1),
                    (d[i][j-1] + 1)),
                    (d[i-1][j-1] + 1)) ;
        }
      }
   
      return d; 
    }
   

   }

My output:

0 1 2 3 4 5 6 7 
1 1 2 3 4 4 5 0 
2 2 1 2 3 4 5 0 
3 3 2 1 2 3 4 0 
4 4 3 2 2 2 3 0 
5 5 4 3 3 3 2 0 
6 0 0 0 0 0 0 0 

The output should be:

0 1 2 3 4 5 6 7 
1 1 2 3 4 5 6 7 
2 2 2 3 4 5 5 6 
3 3 3 2 3 4 5 6 
4 4 4 3 2 3 4 5 
5 5 5 4 3 3 3 4 
6 6 6 5 4 4 4 3 

Answer 1

If you reread the specifications, you will find there are two errors:

• on the wikipedia, they use indices ranging from 1 to (and including n), a string starts at index i=1 according to Wikipedia where it is i=0 in Java; and

• the weights are not updated correctly:

  if (s[i] ==t[j]) 
      d[i][j]=d[i-1][j-1];
  

In the specifications, this should be the minimum of d[i-1][j]+1, d[i][j-1]+1 and d[i-1][j-1]. It is not guaranteed that d[i-1][j-1] is the lowest value, so you should effectively calculate it.

If one takes these mistakes into account, one can modify the table update algorithm (changes on comment //):

for (int j=1;j<=t.length;j++) { //use <= instead of <
    for (int i=1;i<=s.length;i++) { //use <= instead of <
       if (s[i-1] ==t[j-1]) //use i-1 and j-1 
         d[i][j] = Math.min(Math.min(d[i-1][j]+1,d[i][j-1]+1),d[i-1][j-1]); //use the correct update
       else
         d[i][j] = Math.min(Math.min(d[i-1][j]+1,d[i][j-1]+1),d[i-1][j-1]+1);
    }
}