Finding the length of shortest transformation sequence from start to end

Question

Please treat this as a interview at a top tech firm, and share your thoughts on how you think I did. Be honest, and leave no stone unturned.

Problem:

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time. Each intermediate word must exist in the dictionary

For example,

Given:

• start = "hit"
• end = "cog"
• dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Time Complexity: \$O(n^2)\$ (please confirm)

Space complexity: \$O(n)\$

My code:

   private static int ladderLength(String start, String end, HashSet<String> dict) {
        Deque<String> wordSearch = new ArrayDeque<>();
        Deque<Integer> lengthCount = new ArrayDeque<>();
        wordSearch.add(start);
        lengthCount.add(1);
        while(!wordSearch.isEmpty()){
            String analyzing  = wordSearch.poll();
            int curCount = lengthCount.poll();
            if(analyzing.equals(end)){
                return curCount;
            }
            for(int j = 0; j < analyzing.length(); j++){
                for(char i = 'a'; i <= 'z'; i++){
                    char[] possibleMatch = analyzing.toCharArray();
                    possibleMatch[j] = i;
                    String checkMatch = new String(possibleMatch);
                    if(dict.contains(checkMatch)){
                        dict.remove(checkMatch);
                        lengthCount.add(curCount + 1);
                        wordSearch.add(checkMatch);
                    }
                }
            }
        }
        return 0;
   }

Answer 1

First of all, I really liked that your logic doesn't need to compare lengths: as soon as a match is found, it must be one of the shortest lengths, nice! And when the end is unreachable, the method returns 0, an impossible answer (since a valid length must be >= 1), so that's good too.

A couple of things can be improved.

---

Choose the right interfaces

Your method should work with Set<String> dict, and should not limit users to HashSet<String> dict.

Choose the right classes

A Deque is a collection that supports element insertion and removal at both ends. That's more than what you need. A Stack would have been enough for your purpose.

Simplify the inner for loops

The inner for loops are a bit wasteful and can be simplified. You are basically iterating over all possible 1-letter differences and check if in the dictionary. Instead, you could iterate elements of the dictionary and see if they have 1 letter difference. For example like this:

for (String item : dict.toArray(new String[dict.size()])) {
    if (isSingleCharDiff(analyzing, item)) {
        dict.remove(item);
        lengthCount.add(curCount + 1);
        wordSearch.add(item);
    }
}

Discrepancy with the specs

The problem description says:

dict = ["hot","dot","dog","lot","log"]

With this exact input your method returns 0 because it will never reach end. The fix is simple enough, just add it to the dictionary somewhere near the start:

dict.add(end);

A wasted operation

Before the while loop, you do this:

wordSearch.add(start);
lengthCount.add(1);

but then inside the loop you immediately pop them. You could rework the code to eliminate that wasted operation:

String analyzing = start;
int curCount = 1;
while (true) {
    if (analyzing.equals(end)) {
        return curCount;
    }
    for (String item : dict.toArray(new String[dict.size()])) {
        if (isSingleCharDiff(analyzing, item)) {
            dict.remove(item);
            lengthCount.add(curCount + 1);
            wordSearch.add(item);
        }
    }
    if (wordSearch.isEmpty()) {
        break;
    }
    analyzing = wordSearch.pop();
    curCount = lengthCount.pop();
}