Is Levenshtein's distance the right way to tackle this Edit Steps problem?

Question

I'm familiar with Levenshtein's distance, so I decided I would use it to solve UVA's Edit Steps Ladder problem.

My solution is:

import java.io.*;
import java.util.*;

class LevenshteinParaElJuez implements Runnable{
    static String ReadLn(int maxLength){  // utility function to read from stdin,
                                          // Provided by Programming-challenges, edit for style only
        byte line[] = new byte [maxLength];
        int length = 0;
        int input = -1;
        try{
            while (length < maxLength){//Read untill maxlength
                input = System.in.read();
                if ((input < 0) || (input == '\n')) break; //or untill end of line ninput
                line [length++] += input;
            }

            if ((input < 0) && (length == 0)) return null;  // eof
            return new String(line, 0, length);
         }catch (IOException e){
            return null;
        }
    }

    public static void main(String args[]) // entry point from OS
    {
        LevenshteinParaElJuez myWork = new LevenshteinParaElJuez();  // Construct the bootloader
        myWork.run();            // execute
    }

    public void run() {
        new myStuff().run();
    }
}
class myStuff implements Runnable{
    public void run(){

        ArrayList<String> theWords = new ArrayList<String>();
        try
        {

     /// PLACE YOUR JAVA CODE HERE

        String leido=LevenshteinParaElJuez.ReadLn(100);

        //System.out.println("lo leido fue "+leido);

        while (leido.length() != 0){
        theWords.add(leido);
        leido=LevenshteinParaElJuez.ReadLn(100);
        }


        }catch(Exception e){
         System.out.println("El programa genero una excepcion");
        }


        int maxEdit=0;
        int actualEdit=0;

     int wordsIndex1 =0, wordsIndex2=0;


     while (wordsIndex1<= theWords.size())
     {
      while (wordsIndex2<= theWords.size()-1){
         actualEdit=Levenshtein.computeLevenshteinDistance(theWords.get(wordsIndex1),theWords.get(wordsIndex2));
         if (actualEdit>maxEdit){maxEdit=actualEdit;}
         wordsIndex2++;
      }
     wordsIndex1++;

     }

     System.out.println(maxEdit+1);



    }


}
class Levenshtein {
    private static int minimum(int a, int b, int c) {
        if(a<=b && a<=c)
            return a;
        if(b<=a && b<=c)
            return b;
        return c;
    }

    public static int computeLevenshteinDistance(String str1, String str2) {
        return computeLevenshteinDistance(str1.toCharArray(),
                                          str2.toCharArray());
    }

    private static int computeLevenshteinDistance(char [] str1, char [] str2) {
        int [][]distance = new int[str1.length+1][str2.length+1];

        for(int i=0;i<=str1.length;i++)
                distance[i][0]=i;

        for(int j=0;j<=str2.length;j++)
            distance[0][j]=j;

        for(int i=1;i<=str1.length;i++)
            for(int j=1;j<=str2.length;j++)
                distance[i][j]= minimum(distance[i-1][j]+1,
                                        distance[i][j-1]+1,
                                        distance[i-1][j-1]+
                                        ((str1[i-1]==str2[j-1])?0:1));

        return distance[str1.length][str2.length];
    }


}

With this input:

cat
dig
dog
fig
fin
fine
fog
log
wine

it produces the correct output for this sample:

5

The judge is rejecting my answer. This is my first attempt at solving an online judge's problem, and I think I maybe forcing a correct answer here:

 System.out.println(maxEdit+1);

since maxEdit has a value of 4 when computed simply with Levenshtein. Is that what's going on?

Answer 1

The problem states that you are to find the longest lexicographically ordered (i.e. alphabetical) sequence in the dictionary, such that each word in the sequence is formed by adding, deleting, or changing one letter.

So the 5 in the sample result is for the sequence (dig, fig, fin, fine, wine).

I don't think Levenshtein is particularly relevant to this problem, though maybe I am just not imaginative enough. Levenshtein doesn't capture the requirement that each step must be in the dictionary, and later in the dictionary.

Answer 2

Levinshtein is relevant, but will not give you a value used in your output. In this problem, use it to determine if two words have an edit distance of exactly 1, indicating the two words compared are adjacent in the edit step ladder.

Iterate over the words in the dict. and if the next word has an edit distance of 1 from the current word, you may make that the current word, otherwise it must be skipped.

The trick to this problem is finding all possible sequences - just because the next word has an edit distance of 1 doesn't mean using it in the ladder will give you the longest possible ladder.