[LeetCode] 126. Word Ladder II

Posted on | In

Problem

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) 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 an empty list 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
10
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Example 2:

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

Output: []

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

Explanation

  1. First, we build a map, key is each word, value is a list of words that that’s gotten by changing one character of the key word. For example, {"hot": ["dot","hit"]}, {"hit", ["hot"]}. To avoid duplicate, for example, “hot”’s list contains “hit”, and “hit”’s list contains “hot”, so we need to create a doneSet to record which word is already processed to the queue, in other word, if doneSet contains the word, then we wont’ put that word to the queue because we will use BFS.

  2. Similar to 127. Word Ladder, in order to build map, we need to check each character and for each character, we replace it with “a” to “z” and put the new replace word that are in the list to to the map’s key’s corresponding list.

  3. Inside the bfs function, we create a deepsMap, key is each word, value is the distance to the beginWord, so deepsMap.put(beginWord, 0); because distance of beginWord to itself is zero. We do this because some words can also reach the endWord but they cannot reach the beginWord so we want to ignore those words and they will not have depth or in other word, they won’t be inside deepsMap. Also bfs function will return the minLength integer to the endWord.

  4. Then, we use DFS, start from endWord to target is beginWord to trace this route. If the curList size is greater than minLength, we ignore that list. If curList size is equal to minLength, then we check if it’s equal to the beginWord. If it is, then add to the result list. If the curList size is less than the minLength, then we want to find and add the word to our sublist. Here, we will use the deepsMap. If the neightbor word is not in the deepsMap, then ignore it; if it is in the deepsMap but its depth + current depth is greater than minLength, also ignore it; we also need a doneSet to record the word we already traced in this route.

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Solution {
    HashMap<String, List<String>> map = new HashMap<String, List<String>>();
    HashSet<String> doneSet = new HashSet<String>();
    HashMap<String, Integer> deepsMap = new HashMap<String, Integer>();

    public void buildMap(List<String> wordList, String beginWord) {
        HashSet<String> wordSet = new HashSet<String>();
        for (String str : wordList) {
            wordSet.add(str);
        }
        wordSet.add(beginWord);
        for (String str : wordSet) {
            map.put(str, new LinkedList<String>());
            diff(str, wordSet);
        }
    }

    public void diff(String s, HashSet<String> wordSet) {
        for (int i = 0; i < s.length(); i++) {
            StringBuilder sb = new StringBuilder(s);
            char curr = sb.charAt(i);
            for (char c = 'a'; c <= 'z'; c++) {
                if (curr != c) {
                    sb.setCharAt(i, c);
                    if (wordSet.contains(sb.toString())) {
                        map.get(s).add(sb.toString());
                    }
                }
            }
        }
    }

    public int bfs(String beginWord, String endWord, List<String> wordList) {
        if (beginWord.equals(endWord)) return 0;
        Queue<String> queue = new LinkedList<String>();
        queue.offer(beginWord);
        doneSet.add(beginWord);
        deepsMap.put(beginWord, 0);
        int steps = 1;
        while (queue.size() != 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();
                if (curr.equals(endWord)) return steps;
                if (map.containsKey(curr)) {
                    List<String> nxtStrList = map.get(curr);
                    for (String nxtStr : nxtStrList) {
                        if (!deepsMap.containsKey(nxtStr)) {
                            queue.offer(nxtStr);
                            deepsMap.put(nxtStr, steps);
                        }
                    }
                }
            }
            steps++;
        }
        return 0;
    }

    public void DFS(LinkedList<String> currList, List<List<String>> results, String target, int minLength,
            int currDeep) {
        String currString = currList.get(0);
        if (currList.size() > minLength) return;
        else if (currList.size() == minLength) {
            if (currString.equals(target)) {
                results.add(new LinkedList<String>(currList));
            }
        } else {
            for (String str : map.get(currString)) {
                if (!doneSet.contains(str) && deepsMap.containsKey(str) && deepsMap.get(str) + currDeep < minLength) {
                    currList.addFirst(str);
                    doneSet.add(str);
                    DFS(currList, results, target, minLength, currDeep + 1);
                    doneSet.remove(str);
                    currList.removeFirst();
                }
            }
        }
    }

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        buildMap(wordList, beginWord);
        int minLength = bfs(beginWord, endWord, wordList);
        doneSet.clear();
        LinkedList<String> currList = new LinkedList<String>();
        List<List<String>> results = new LinkedList<List<String>>();
        currList.add(endWord);
        doneSet.add(endWord);
        DFS(currList, results, beginWord, minLength, 1);
        return results;
    }
}