[LeetCode] 127. Word Ladder

Posted on | In

Problem

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

1
2
3
4
5
6
7
8
9
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

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

Example 2:

1
2
3
4
5
6
7
8
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Explanation

  1. If we solve this problem manually, for example from example1, we will find whether “cit” is in the list, no; we try “hot”, yes, it is in the list; then we try “cot” or “hog”, they both not in the list. This method is not working.

  2. We can try brute force. For every character in the word, we try to replace each character with ‘a’ to ‘z’. For example, “hit”, we replace the first character with “a”, so it is “ait”; replace it with “b”, so it is “bit”; and we get “cit”, “dit”, “eit”, …, “zit”. We check if these words if it’s the endWord, if not, check if they are in the list, if the word is in the list, then it can potentially be the path to get the endWord.

  3. Now, if the word we try is “hot”, and we check it’s in the list, then should we try “hpt”, “hqt”, “hrt”… (BFS) or “aot”, “bot”, “cot”… (DFS)? We know that it’s better to use BFS to find the minimum path, so it’s better to use BFS.

  4. In order to improve the performance of searching if the word is in the list, we can put the list of words to a hash set. To use BFS, we need to have a queue. First, put the beginWord to the queue, and pop it out as popWord and try to replace its each character with “a” to “z”. We initialize the res to 2 since that’s the minimum because one is beginWord and antoher one is endWord. Then if the popWord is the same as endWord, we can just return res. If it’s not equal endWord but it’s in the list, then we push it to the queue and increase the level by 1. If this time, the new popWord is the same as the endWord, we can just return result+level.

  5. We use the queue size to keep track when we should update level by 1. After we pop queueSize elements, then we can increase level by 1.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> hs = new HashSet<>();
        for (String s : wordList) {
            hs.add(s);
        }
        if (!hs.contains(endWord)) return 0;
        Queue<String> queue = new LinkedList<>();
        int res = 2;
        int level = 0;
        queue.offer(beginWord);

        while (!queue.isEmpty()) {
            for (int n = queue.size(); n > 0; n--) {
                String popWord = queue.poll();
                for (int i = 0; i < popWord.length(); i++) {
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        String s = popWord.substring(0, i)+ch+popWord.substring(1+i);
                        if (s.equals(endWord)) {
                            res += level;
                            return res;
                        }
                        else if (hs.contains(s)) {
                            queue.add(s);
                            hs.remove(s);
                        }
                    }
                }
            }
            level += 1;
        }

        return 0;
    }
}