# 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<String> dict) {
Deque<String> wordSearch = new ArrayDeque<>();
Deque<Integer> lengthCount = new ArrayDeque<>();
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);
}
}
}
}
return 0;
}

• Commented Aug 13, 2016 at 23:03

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


### 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);


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

• You implementation doesn't use any unique features of a HashSet. It would work just the same with any other Set, for example a TreeSet. Using a Set is good enough for your case, and allows the widest possible uses. Commented Apr 26, 2014 at 18:37