この編集ステップの問題には、Levenshteinの距離が適切ですか？

Question

私はレーベンシュタインの距離に精通してるので、私は、私は私のソリューションがあるUVA's Edit Steps Ladder problem.

を解決するためにそれを使用することを決めた：

cat 
dig 
dog 
fig 
fin 
fine 
fog 
log 
wine 

はそれが正しいを生成します。この入力で

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]; 
    } 


} 

このサンプルの出力：

5 

裁判官は私の答えを拒否しています。これは、オンライン裁判官の問題を解決するために、私の最初の試みである、と私は多分ここに正しい答えを強制的に考えて：

System.out.println(maxEdit+1); 

maxEditは、レーベンシュタインと単純に計算された4の値を有しているからです。それは何が起こっているのですか？

Answer 1

Levinshteinは関連していますが、あなたの出力に値を与えません。この問題では、2つの単語の編集距離が正確に1であるかどうかを判断するために使用します。これは、編集ステップのラダーで比較された2つの単語が隣接していることを示します。

dictの単語を繰り返します。次の単語の編集距離が現在の単語から1の場合、はとなり、それ以外の場合はスキップする必要があります。

すべて可能なシーケンス - 次の単語の編集距離が1であるということは、ラダーで使用することを意味するものではありません。

Answer 2

辞書の（つまりアルファベット順）のシーケンスの中で最も長い単語がであることがわかります。その結果、1つの文字を追加、削除、または変更して各単語を構成します。

サンプル結果の5は、シーケンス（dig、fig、fin、fine、wine）のものです。

私はLevenshteinが特にこの問題に関連しているとは思わないが、多分私は想像力が足りないかもしれない。 Levenshteinは、各ステップが辞書に入っていて、後で辞書になければならないという要件を捉えていません。