[LeetCode 127] Word Ladder

Question

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.

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

This question is find shortest path, so we shall choose BFS over DFS.
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).
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)在本层我们就能遍历到该元素。也就是说，我们到达这个元素有两条路径，而且它们都是最短路径。

对于本题来说，是没有什么影响的，因为到dog距离都是3，到dig距离都是4。但是后面我们做word ladder 2的时候，如果没有考虑这个情况，将是非常致命的，因为题目要求输出最短路径的所有情况

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

Woodstock Blog

a tech blog for general algorithmic interview questions