Finding the length of shortest transformation sequence from start to end 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&lt;String&gt; dict) {
        Deque&lt;String&gt; wordSearch = new ArrayDeque&lt;&gt;();
        Deque&lt;Integer&gt; lengthCount = new ArrayDeque&lt;&gt;();
        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 &lt; analyzing.length(); j++){
                for(char i = 'a'; i &lt;= '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;
   }
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&lt;String&gt; dict, and should not limit users to HashSet&lt;String&gt; 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();
}