I wrote a program that calculates the minimum number of rungs of a "word ladder" between a starting word and an ending word. The function minlinks()
takes in 3 arguments: a list which acts as a dictionary, a starting word, and an ending word. It returns an int[]
of two values; the first is minimum number of links in the word ladder, the second is the number of paths with said number of links.
Example of a word ladder:
words = [rain, ruin, gain, grin, grit, main, pain, pair, pail, mail] from = sail to = ruip
Returns: [6, 2]
There are two links of length six and no shorter links.
sail mail main rain ruin ruip
sail pail pain rain ruin ruip
As written, the program works. However, as someone new to coding in Java, I would appreciate others commenting on the coding style. Also, I included a test case in the main method which runs in about 4 seconds on my computer, which is too slow. Is there any way to optimize this program to make it run faster?
import java.util.*;
public class WordLinksMin {
// Helper method, returns true if two words are one letter away from each other.
public boolean isStep(String from, String s) {
if (from.length() != s.length()) {
return false;
}
int differences = 0;
for (int charIndex = 0; charIndex < from.length(); charIndex++) {
if (from.charAt(charIndex) != s.charAt(charIndex)) {
differences++;
}
if(differences > 1) break;
}
return (differences == 1);
}
// given an array of words (our "dictionary"), the starting word and the ending word. find the minimum number of links between start and end using the given dictionary.
// function returns int[] array {min number of links, number of paths with min number of links}
public int[] minLinks(String[] words, String start, String end) {
int firstFindSize = 0;
int[] result = new int[2];
// Convert String[] into a HashSet.
List < String > myWordList = new ArrayList < String > (Arrays.asList(words));
Set < ArrayDeque < String >> allStacks = new HashSet < ArrayDeque < String >> ();
if (myWordList.size() == 0) return result;
// We will implement BFS with a stack of queues
ArrayDeque < ArrayDeque < String >> wordQueue = new ArrayDeque < ArrayDeque < String >> (); //one queue of stacks to track nodes visited
// initialize the parent node, which is a stack containing starting word.
ArrayDeque < String > startStack = new ArrayDeque < String > ();
startStack.push(start);
wordQueue.add(startStack);
// we act differently in while loop based on whether we have already found a path from start to end
boolean firstFind = true;
while (!wordQueue.isEmpty()) {
ArrayDeque < String > currentStack = wordQueue.pop();
String currentWord = currentStack.peek();
if (isStep(currentWord, end) && currentStack.size() >= 2 && firstFind) { //no direct link
currentStack.push(end);
allStacks.add(currentStack);
firstFind = false; //after finding first stack, we know the stack size we must look for, for any other path of the same length.
firstFindSize = currentStack.size();
//System.out.println((firstFindSize));
//System.out.println("before ff");
//System.out.println(currentStack);
} else if (isStep(currentWord, end) && currentStack.size() == firstFindSize - 1 && !firstFind) {
currentStack.push(end);
//System.out.println("not ff");
//System.out.println(currentStack);
allStacks.add(currentStack);
}
if (firstFind) {
for (String word: myWordList) {
if (isStep(currentWord, word) && !currentStack.contains(word)) {
ArrayDeque < String > wordStack = new ArrayDeque < String > (currentStack);
wordStack.push(word);
wordQueue.add(wordStack);
}
}
}
}
result[1] = allStacks.size();
result[0] = firstFindSize;
System.out.printf("%d %d", result[0], result[1]);
return result;
}
public static void main(String[] args) {
WordLinksMin a = new WordLinksMin();
String[] b = {
"abcde", "abcda", "abcdb", "abcdc", "abcdd", "abcdf", "abcdg", "abcdh", "abcdi", "abcdj", "abcdk", "obcda", "obcdb", "obcdc", "obcdd", "obcdf", "obcdg", "obcdh", "obcdi", "obcdj", "obcdk", "obcdm", "obadm", "obbdm", "obddm", "obedm", "obfdm", "obgdm", "obhdm", "obidm", "objdm", "obkdm", "okadm", "okbdm", "okddm", "okedm", "okfdm", "okgdm", "okhdm", "okidm", "okjdm", "okkdm", "okodm", "okokm"
};
long startTime = System.nanoTime();
System.out.println(a.minLinks(b, "abode","okoko"));
long endTime = System.nanoTime();
long duration = (endTime - startTime);
System.out.println(duration);
// for (List<String> list : a.listOfPaths){
// for (String s : list) {
// System.out.print(s+" ");
// }
// System.out.println();
// }
}
}