Skip to content

Instantly share code, notes, and snippets.

@hnabbasi
Created February 14, 2023 02:23
Show Gist options
  • Save hnabbasi/cf453a9de41977a834ba9765f628e910 to your computer and use it in GitHub Desktop.
Save hnabbasi/cf453a9de41977a834ba9765f628e910 to your computer and use it in GitHub Desktop.
Word Ladder assignment
package org.example;
import java.io.File;
import java.io.FileNotFoundException;
import java.net.URISyntaxException;
import java.util.*;
public class Main {
private static final Queue<Stack<String>> stackQueue = new LinkedList<>();
private static final Set<String> visitedWords = new HashSet<>();
public static void main(String[] args) throws FileNotFoundException, URISyntaxException {
var result = findWordLadder("code", "data", "FoursDictionary.txt");
System.out.println(result);
}
private static WordsDictionary getDictionary(String fileName) throws URISyntaxException, FileNotFoundException {
var dictionaryFile = new File(Objects.requireNonNull(Main.class.getClassLoader().getResource(fileName)).toURI().getPath());
return new WordsDictionary(dictionaryFile);
}
public static Stack<String> findWordLadder(String beginWord, String endWord, String dictionaryFileName) throws FileNotFoundException, URISyntaxException {
var dictionary = getDictionary(dictionaryFileName);
Stack<String> initialStack = new Stack<>();
initialStack.add(beginWord);
visitedWords.add(beginWord);
stackQueue.add(initialStack);
while(!stackQueue.isEmpty()){
var stack = stackQueue.poll();
var topWord = stack.peek();
if(topWord.equals(endWord)){
return stack;
}
var n = topWord.length();
for (var i=0; i<n; i++) {
for(var j='a'; j<='z'; j++) {
if(topWord.charAt(i) == j)
continue;
var newWord = topWord.replace(topWord.charAt(i), j);
if(!dictionary.contains(newWord) || visitedWords.contains(newWord))
continue;
var newStack = (Stack<String>) stack.clone();
newStack.push(newWord);
stackQueue.add(newStack);
visitedWords.add(newWord);
}
}
}
return new Stack<>();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment