# [LeetCode 127] Word Ladder

### Question

link

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

1. Only one letter can be changed at a time
2. 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.

### Stats

 Frequency 5 Difficulty 3 Adjusted Difficulty 5 Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

This is an extremely difficult question.

### Solution

1. This question is find shortest path, so we shall choose BFS over DFS.

2. Since finding an element in HashSet is O(1) time, we can generate all the possible strings of distance = 1 and check if they are in the dictionary. In this way, we reduce time complexity from O(m x n) to O(m x 26).

3. If a word is found from the dictionary, remove it.

For the 3rd point, we remove the word from dict. It might be hard to understand. This blog explains it clear enough.

1.以后再也遍历不到这个元素，那么我们删除它当然没有任何问题。

2.我们以后会遍历到该元素，又分为两种情况：

(1)在本层我们就能遍历到该元素。也就是说，我们到达这个元素有两条路径，而且它们都是最短路径。

(2)在更下层我们才能够遍历到该元素。比如hot->dot->dog->dig和hot->hat->dat->dag->dog->dig，如果第一次我们找到了dog并且将其删除，那么第二次我们实际上是找不到这个元素的。这样对于本题来说，没有任何影响。对于word ladder 2来说，因为也是要输出最短路径，所以也不会有任何影响。

### Code

BFS solution

This is similar to the code posted in this article.

``````public int ladderLength(String start, String end, HashSet<String> dict) {
if (start.equals(end)) return 1;
LinkedList<String> words = new LinkedList<String>();
LinkedList<Integer> nums = new LinkedList<Integer>();
words.add(start);
nums.add(1);
while (!words.isEmpty()) {
String word = words.remove();
int num = nums.remove();
// otherwise, change each char in word, and find it from dict
char[] charArr = word.toCharArray();
for (int i = 0; i < charArr.length; i++) {
char originChar = charArr[i];
for (char j = 'a'; j <= 'z'; j++) {
charArr[i] = j;
String newWord = new String(charArr);
if (newWord.equals(end))
return num + 1;
if (dict.contains(newWord)) {
dict.remove(newWord);
words.add(newWord);
nums.add(num + 1);
}
}
charArr[i] = originChar;
}
}
return 0;
}
``````