[LeetCode] Problem 126 - Word Ladder II

Posted on | In ,

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

No.1

Input:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

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

No.2

Input:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

Output: []

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

Code

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
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    List<List<String>> results = new ArrayList<>();
    List<String> result = new ArrayList<>();

    if (!wordList.contains(endWord))
        return results;

    Map<String, List<String>> prev = new HashMap<>();
    Map<String, Integer> count = new HashMap<>();
    Set<String> dict = new HashSet<>();

    dict.add(beginWord);
    dict.add(endWord);
    prev.putIfAbsent(beginWord, new ArrayList<>());
    prev.putIfAbsent(endWord, new ArrayList<>());
    count.put(endWord, 0);

    for (String word : wordList)
        dict.add(word);

    // end -> start
    bfs(prev, count, dict, endWord);

    // start -> end
    dfs(results, result, prev, count, beginWord, endWord);

    return results;
}

private void bfs(Map<String, List<String>> prev, Map<String, Integer> count, Set<String> dict, String start) {
    Queue<String> queue = new LinkedList<>();
    queue.offer(start);

    while (!queue.isEmpty()) {
        String current = queue.poll();

        List<String> nexts = new ArrayList<>();

        for (int i = 0; i < current.length(); i++) {
            char[] newWord = current.toCharArray();

            for (char ch = 'a'; ch <= 'z'; ch++) {
                if (newWord[i] == ch)
                    continue;

                newWord[i] = ch;
                String str = String.valueOf(newWord);

                if (dict.contains(str))
                    nexts.add(str);
            }
        }

        for (String next : nexts) {
            prev.putIfAbsent(next, new ArrayList<>());
            prev.get(next).add(current);

            if (!count.containsKey(next)) {
                count.put(next, count.get(current) + 1);
                queue.offer(next);
            }
        }
    }
}

private void dfs(List<List<String>> results, List<String> result, Map<String, List<String>> prev, Map<String, Integer> count, String start, String end) {
    result.add(start);

    if (start == end)
        results.add(new ArrayList<>(result));
    else {
        List<String> nexts = prev.get(start);

        for (String next : nexts) {
            if (count.get(start) == count.get(next) + 1)
                dfs(results, result, prev, count, next, end);

        }
    }

    result.remove(result.size() - 1);
}