Ошибка программы Java Word Ladder Ошибка переполнения стека

Question

Мне нужно написать код в java для программы словесной лестницы. Инструкции заключаются в следующем:

Напишите программу, используя рекурсию, чтобы найти слово лестнице дано начала слово и конечное слово, или определяет, если ни одно слово лестница не существует. Используйте файл "words.txt" как словарь действительных слов. Это файл содержит 87314 слов. В вашей программе не нужно найти кратчайшую словесную лестницу между словами, любое слово-лестница будет делать, если один существует.

Например, начиная с рыбы, которую вы можете сделать слово лестница с тучными по следующей лестнице:
                  FISH, WISH, ВСГ, MASH, МАСТ

Вот ссылка для words.txt

Я чувствую, что мой код очень близок к работе, но я получаю нг ошибку переполнения стека на моем выходе:

Exception in thread "main" java.lang.StackOverflowError 
    at java.io.FileOutputStream.write(FileOutputStream.java:326) 
    at java.io.BufferedOutputStream.flushBuffer(BufferedOutputStrea‌​m.java:82) 
    at java.io.BufferedOutputStream.flush(BufferedOutputStream.java‌​:140) 
    at java.io.PrintStream.write(PrintStream.java:482) 
    at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221) 
    at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:‌​291) 
    at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104) 
    at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.ja‌​va:185) 

Мой код выглядит следующим образом:

импорт java.util.Scanner; import java.io.FileNotFoundException; import java.io.FileInputStream; импорт java.io.File; import java.io.FileReader; импорт java.io.PrintWriter; import java.io.FileOutputStream;

public class C11PP8 
{ 
    public static void main(String[] args) 
    { 
    Scanner inputStream = null; 
    PrintWriter outputStream = null; 
    int numWords = 0; 
    String wordRead = ""; 
    String[] wordLibrary; 
    String startWord, endWord; 
    Scanner keyboard = new Scanner(System.in); 
    int i; 


    //open for writing four letter words 
    try 
    { 
     outputStream = new PrintWriter(new FileOutputStream("FourLetterWords.txt")); 
    }//end try 

    catch(FileNotFoundException e) 
    { 
     System.out.println("File not found, program will close."); 
     System.exit(0); 
    }//end catch 


    //open for reading all words 
    try 
    { 
     inputStream = new Scanner(new FileReader("words.txt")); 

    }//end try 

    catch(FileNotFoundException e) 
    { 
     System.out.println("File not found, program will close."); 
     System.exit(0); 
    }//end catch 

    while(inputStream.hasNextLine()) 
    { 
     wordRead = inputStream.nextLine(); 
     if(wordRead.length() == 4) 
     { 
     wordRead = wordRead.toLowerCase(); 
     outputStream.println(wordRead); 
     } 
    }//end while loop 

    inputStream.close(); 
    outputStream.close(); 

    //open for reading to count number of words 
    try 
    { 
     inputStream = new Scanner(new FileReader("FourLetterWords.txt")); 

    }//end try 

    catch(FileNotFoundException e) 
    { 
     System.out.println("File not found, program will close."); 
     System.exit(0); 
    }//end catch 

    while(inputStream.hasNextLine()) 
    { 
     inputStream.nextLine(); 
     ++numWords; 
    }//end while loop 

    inputStream.close(); 

    //declare 
    wordLibrary = new String[numWords]; 

    //open FourLetterWord to read 
    //and populate the array of words 
    try 
    { 
     inputStream = new Scanner(new FileReader("FourLetterWords.txt")); 

    }//end try 

    catch(FileNotFoundException e) 
    { 
     System.out.println("File not found, program will close."); 
     System.exit(0); 
    }//end catch 

    i = 0; 
    while(inputStream.hasNextLine()) 
    { 
     wordLibrary[i] = inputStream.nextLine(); 
     ++i; 
    }//end while loop 

    inputStream.close(); 

    //confirm 
    //for(i = 0; i < wordLibrary.length; ++i) 
    // System.out.println(wordLibrary[i]); 

    //user input 
    do 
    { 
     System.out.println("Enter your 4 letter start word: "); 
     startWord = keyboard.nextLine(); 
    }while(startWord.length() != 4); 
    startWord = startWord.toLowerCase(); 

    do 
    { 
     System.out.println("Enter your 4 letter end word: "); 
     endWord = keyboard.nextLine(); 
    }while(endWord.length() != 4); 
    endWord = endWord.toLowerCase(); 

    //call the recursive method 
    findTheWord(startWord, endWord, wordLibrary); 

    }//end main 

    public static void findTheWord(String startWordPassed, String endWordPassed, String[] libraryPassed) 
    { 
    String currentWord = ""; 
    int count = 0; 
    //base case 
    if(endWordPassed.equals(startWordPassed)) 
    { 
     System.out.println("Word found: " + endWordPassed); 
    }//end if 
    else 
    { 
     //change a single letter of the startWordPassed and make that the new startWordPassed 
     // if the new word is in the array 

     //OR 

     //iterate through the array and find a word that is only one letter different than startWordPassed 
     //make that the new startWordPassed 

     for(int i = 0; i < libraryPassed.length; ++ i) 
     { 
     currentWord = libraryPassed[i]; 
     for(int j = 0; j < startWordPassed.length(); ++ j) 
     { 
      if(startWordPassed.charAt(j) == currentWord.charAt(j)) 
      ++count; 
     }//end for loop 
     if(count == 3) 
     libraryPassed[i] = " "; 
     }//end for loop 
     System.out.println(currentWord); 
     startWordPassed = currentWord; 
     //recursive call 
     findTheWord(startWordPassed, endWordPassed, libraryPassed); 
    }//end else 
    }//end method 

}//end class 

Выход, который я получаю, представляет собой несколько «zuni», а затем переполнение стека. «zuni» - это последнее 4-буквенное слово в текстовом документе.

Любая помощь, связанная с тем, чтобы это правильно работало, будет принята с благодарностью.

Answer 1

Используйте этот метод для «findTheWord», и вы получите результаты, как вы хотели

public static void findTheWord(String startWordPassed, 
     String endWordPassed, String[] libraryPassed) { 
    String currentWord = ""; 
    int count = 0; 
    // base case 
    if (endWordPassed.equals(startWordPassed)) { 
     System.out.println("Word found: " + endWordPassed); 
    }// end if 
    else { 
     // change a single letter of the startWordPassed and make that the 
     // new startWordPassed 
     // if the new word is in the array 

     // OR 
     Map<String, Integer> index = new HashMap<String, Integer>(); 

     for (int i = 0; i < libraryPassed.length; i++) { 
      index.put(libraryPassed[i], i); 
     } 
     System.out.println("Start Index:" + index.get(startWordPassed)); 
     System.out.println("End Index:" + index.get(endWordPassed)); 
     // iterate through the array and find a word that is only one letter 
     // different than startWordPassed 
     // make that the new startWordPassed 
     System.out.println("Start Word:" + startWordPassed); 
     int startIndex = index.get(startWordPassed) + 1; 
     int endIndex = index.get(endWordPassed); 
     for (int i = startIndex; i < endIndex; i++) { 
      currentWord = libraryPassed[i]; 
      //System.out.println("current word:"+currentWord); 
      count = 0; 
      for (int j = 0; j < startWordPassed.length(); ++j) { 
       if (startWordPassed.charAt(j) == currentWord.charAt(j)) 
        ++count; 
      }// end for loop 
      if (count == 3) 
      { 
       startWordPassed = currentWord; 
       System.out.println("Ladder Word:"+startWordPassed); 
      } 
     }// end for loop 
    }// end else 
}// end method 

Answer 2

Ваш рекурсивный метод должен возвращать что-то для того, чтобы программа для обнаружения, когда рекурсия должна быть остановлена.

Кроме того, вызов вашего рекурсивного метода следует вызывать, только если условие выполнено (count == 3).

Замените метод findTheWord() с:

public static boolean findTheWord(String startWordPassed, String endWordPassed, String[] libraryPassed) 
{ 
    String currentWord = ""; 
    //base case 
    if(endWordPassed.equals(startWordPassed)) 
    { 
     System.out.println("Word found: " + endWordPassed); 
     return true; 
    }//end if 
    else 
    { 
     for(int i = 0; i < libraryPassed.length; ++ i) 
     { 
      currentWord = libraryPassed[i]; 
      int count = 0; 
      for(int j = 0; j < startWordPassed.length(); ++ j) 
      { 
       if(startWordPassed.charAt(j) == currentWord.charAt(j)) 
        ++count; 
      }//end for loop 
      if(count == 3) { 
       libraryPassed[i] = " "; 
       System.out.println(currentWord); 
       startWordPassed = currentWord; 
       //recursive call 
       if (findTheWord(startWordPassed, endWordPassed, libraryPassed)) { 
        return true; 
       } 
      } 
     }//end for loop 
    }//end else 

    return false; 
}//end method 

Для того, чтобы покрыть случай, когда нет лестницы не существует, то вы можете использовать возвращаемое значение findTheWord() из главного метода:

public static void main(String[] args) { 
    ... 
    ... 
    //call the recursive method 
    if (!findTheWord(startWord, endWord, wordLibrary)) { 
     System.out.println("No ladder exists"); 
    } 
}