Word ladder finding class

Question

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;
}

}

Answer 1

My few problems:

1. Instead HashSet<String> tempDict = (HashSet<String>) this.dictionary.clone(); you could simply use Set<String> tempDict = new HashSet<>( this.dictionary );. You will avoid ugly @SuppressWarnings("unchecked").
2. Parsing input could be performed in other method while this one would accept two strings: initial and final word. That way it's much more versatile like Sharon Ben Asher mentioned.
3. Code most likely works but you just can't see what is really doing. Either commenting or extracting vital parts of algorithm into named methods would most likely shed some light.

I would really suggest trying to implement graph based algorithm where nodes are words and edges connect words with distance of 1. That way you could construct Graph once and use for example Dijkstra's algorithm to determine shortest path between two given nodes if it exists. Complexity would be O(n^2) where n is number of words. It could be a bit more intuitive with a bit of an explanation and possibly faster on multiple runs.

Answer 2

Fist of all, the code doesn't work. here's my test method. I get an empty response.

public static void main(String... args) {

    HashSet<String> dictionary = new HashSet<>();
    dictionary.add("abcd");
    dictionary.add("abce");
    dictionary.add("abcf");
    dictionary.add("abcg");
    dictionary.add("abch");
    dictionary.add("abxd");
    dictionary.add("abxh");

    WordLadder wd = new WordLadder(dictionary);
    System.out.println(wd.findLadder("abcd abch"));

}

However, assuming you fix this, here is my review

1. API definition: the api you chose is counter-intuitive. why not accept two string words?
2. code to the interface: if you meant words to be a LIFO stack, use the Stack interface of push() and pop(). there are two reason for that: one is that it makes the usage of words clearer to another human. more importantly - how do you that LinkedList add() is doing the same as push()?
3. the method violates the single responsibility principle. it is parsing the input, it searches for a word in the dictionary and all the other stuff. what if you wanted to have another data structure for the dictionary? or put it in a DB?