JAVA Program The word ladder game was invented by Lewis Carroll in 1877. The ide
ID: 3573275 • Letter: J
Question
JAVA Program
The word ladder game was invented by Lewis Carroll in 1877. The idea is to begin with a start word and change one letter at a time until arriving at an end word. Each word along the way must be an English word.
For example. starting from FISH you can make a word ladder to MAST through the following ladder:
FISH. WISH, WASH, MASH, MAST
Write a program that uses recursion to find the word ladder given a start word and an end word. or determines if no word ladder exists. Use the file words.txt that is available online with the source code for the book as your dictionary of valid words. This file contains 87314 words. Your program does not need to find the shortest word ladder between words. any word ladder will do if one exists.
Explanation / Answer
Please find attached code and it's output.
package javaapplication8;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
public class WordLadderSolver{
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
Set<String> dictionary = new HashSet<String>();
try (BufferedReader br = new BufferedReader(new FileReader("words.txt"))) {
String sCurrentLine;
while ((sCurrentLine = br.readLine()) != null) {
dictionary.add(sCurrentLine);
}
} catch (IOException e) {
e.printStackTrace();
}
System.out.println("Enter Start Word:");
String startWord = in.nextLine();
System.out.println("Enter End Word:");
String endWord = in.nextLine();
Ladder result = getShortestTransformationIterative(startWord, endWord, dictionary);
//Ladder result = getShortestTransformationRecursive(startWord, endWord, dictionary);
if(result!=null){
System.out.println("Length is "+result.getLength() + " and path is :"+ result.getPath());
}else{
System.out.println("No Path Found");
}
}
private static Ladder getShortestTransformationIterative(String startWord, String endWord, Set<String> dictionary){
if(dictionary.contains(startWord) && dictionary.contains(endWord)){
List<String> path = new LinkedList<String>();
path.add(startWord);
//All intermediate paths are stored in queue.
Queue<Ladder> queue = new LinkedList<Ladder>();
queue.add(new Ladder(path, 1, startWord));
//We took the startWord in consideration, So remove it from dictionary, otherwise we might pick it again.
dictionary.remove(startWord);
//Iterate till queue is not empty or endWord is found in Path.
while(!queue.isEmpty() && !queue.peek().equals(endWord)){
Ladder ladder = queue.remove();
if(endWord.equals(ladder.getLastWord())){
return ladder;
}
Iterator<String> i = dictionary.iterator();
while (i.hasNext()) {
String string = i.next();
if(differByOne(string, ladder.getLastWord())){
List<String> list = new LinkedList<String>(ladder.getPath());
list.add(string);
//If the words differ by one then dump it in Queue for later processsing.
queue.add(new Ladder(list, ladder.getLength()+1, string));
//Once the word is picked in path, we don't need that word again, So remove it from dictionary.
i.remove();
}
}
}
//Check is done to see, on what condition above loop break,
//if break because of Queue is empty then we didn't got any path till endWord.
//If break because of endWord matched, then we got the Path and return the path from head of Queue.
if(!queue.isEmpty()){
return queue.peek();
}
}
return null;
}
private static Ladder getShortestTransformationRecursive(String startWord, String endWord, Set<String> dictionary){
//All Paths from startWord to endWord will be stored in "allPath"
LinkedList<Ladder> allPath = new LinkedList<Ladder>();
// Shortest path will be stored in "shortestPath"
Ladder shortestPath = new Ladder(null);
List<String> path = new LinkedList<String>();
path.add(startWord);
recursiveHelperShortest(startWord, endWord, dictionary, new Ladder(path, 1, startWord), allPath, shortestPath);
return shortestPath;
}
private static void recursiveHelperShortest(String startWord, String endWord, Set<String> dictionary, Ladder ladder, LinkedList<Ladder> allPath, Ladder shortestPath){
if(ladder.getLastWord().equals(endWord)){
// For storing all paths
allPath.add(new Ladder(new LinkedList<String>(ladder.getPath())));
//For storing the shortest path from among all paths available
if(shortestPath.getPath()==null || shortestPath.getPath().size()>ladder.getPath().size()){
shortestPath.setPath(new LinkedList<String>(ladder.getPath()));
shortestPath.setLength(ladder.getPath().size());
}
return;
}
Iterator<String> i = dictionary.iterator();
while (i.hasNext()) {
String string = i.next();
if(differByOne(string, ladder.getLastWord()) && !ladder.getPath().contains(string)){
List<String> path = ladder.getPath();
path.add(string);
//We found the new word in intermediate path, Start exploring new word from scratch again.
recursiveHelperShortest(startWord, endWord, dictionary, new Ladder(path, ladder.getLength()+1, string), allPath, shortestPath);
//After exploring new word, remove it from intermediate path.
path.remove(path.size()-1);
}
}
}
private static boolean differByOne(String word1, String word2){
if (word1.length() != word2.length()) {
return false;
}
int diffCount = 0;
for (int i = 0; i < word1.length(); i++) {
if (word1.charAt(i) != word2.charAt(i)) {
diffCount++;
}
}
return (diffCount == 1);
}
}
======Ladder.java====
package javaapplication8;
import java.util.List;
class Ladder{
private List<String> path; //For storing path
private String lastWord; //For storing last word of path
private int length; //Length of the path.
public Ladder(List<String> path) {
this.path=path;
}
public Ladder(List<String> path, int length, String lastWord) {
this.path=path;
this.length=length;
this.lastWord=lastWord;
}
public List<String> getPath() {
return path;
}
public int getLength() {
return length;
}
public String getLastWord() {
return lastWord;
}
public void setPath(List<String> path) {
this.path = path;
}
public void setLength(int length) {
this.length = length;
}
}
====O/P===
Enter Start Word:
cat
Enter End Word:
dog
Length is 4 and path is :[cat, cot, cog, dog]
Let me know if you have ay doubts.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.