I have a class that I'm using to find the shortest word ladder between two words. Each "Step" in that ladder is returned as a String
element in a LinkedList
. If it can't find one, it returns an empty LinkedList
. The class is only intended to work with capital letters.
A step can only be formed from a word in the HashSet<String>
dictionary variable.
I haven't made anything like this before, and I'm posting here because I'd appreciate help making it run faster and advice regarding how to make the code itself more easily read by other humans.
public class WordLadder {
private HashSet<String> dictionary;
public WordLadder(HashSet<String> dictionary) {
this.dictionary = dictionary;
}
/**
* This method finds the shortest word ladder between two words and returns
* it as a LinkedList of Strings.
*
* @return LinkedList of Strings.
*/
@SuppressWarnings("unchecked")
public LinkedList<String> findLadder(String input) {
// this method relies on deleting entries from a HashSet
HashSet<String> tempDict = (HashSet<String>) this.dictionary.clone();
// create LinkedLists
LinkedList<Integer> distances = new LinkedList<>();
LinkedList<LinkedList<String>> ladders = new LinkedList<>();
LinkedList<String> words = new LinkedList<>();
// split the input line into the starting and ending words
String startWord = input.substring(0, input.indexOf(" "));
String endWord = input.substring(input.indexOf(" ") + 1);
// holds the shortest ladder found
LinkedList<String> shortestLadder = new LinkedList<>();
words.add(startWord);
distances.add(1);
ladders.add(new LinkedList<>(Arrays.asList(startWord)));
while (!words.isEmpty()) {
Integer distance = distances.pop();
LinkedList<String> ladder = ladders.pop();
String word = words.pop();
// has the shortest ladder been found?
if (word.equals(endWord)) {
shortestLadder = ladder;
}
for (int i = 0; i < word.length(); i++) {
char[] currCharArr = word.toCharArray();
for (char c = 'A'; c <= 'Z'; c++) {
currCharArr[i] = c;
LinkedList<String> currentPathQueueTemp = new LinkedList<>(ladder);
String newWord = new String(currCharArr);
if (tempDict.contains(newWord)) {
words.add(newWord);
ladders.add(currentPathQueueTemp);
tempDict.remove(newWord);
distances.add(distance + 1);
currentPathQueueTemp.add(newWord);
}
}
}
}
return shortestLadder;
}
}