kniost

谁怕，一蓑烟雨任平生

0%

LeetCode 126. Word Ladder II

发表于 分类于
本文字数： 3.5k 阅读时长 ≈ 3 分钟
LeetCode 126. Word Ladder II

126. Word Ladder II

Difficulty:: Hard

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
7
8
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: []

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

Solution

Language: Java

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
class Solution {
      public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            List<List<String>> result = new ArrayList<>();
            if (beginWord == null || endWord == null || beginWord.length() != endWord.length() ||
                  wordList == null || wordList.size() == 0) {
                  return result;
           } 
            Map<String, List<String>> graph = new HashMap<>();
            Map<String, Integer> dMap = new HashMap<>();
            Set<String> wordSet = new HashSet<>(wordList);
            wordSet.add(beginWord);
            if (!wordSet.contains(endWord)) {
                  return result;
           }
            bfs(beginWord, endWord, wordSet, dMap, graph);
            dfs(beginWord, endWord, dMap, graph, result, new ArrayList<>());
            return result;
     }
      
      private void bfs(String beginWord, String endWord, Set<String> wordSet, Map<String, Integer> dMap, Map<String, List<String>> graph) {
            Queue<String> q = new LinkedList<>();
            q.offer(endWord);
            dMap.put(endWord, 0);
            int paces = 0;
            for (String s : wordSet) {
                  graph.put(s, new ArrayList<String>());
           }
            while(!q.isEmpty()) {
                  paces++;
                  int size = q.size();
                  for (int i = 0; i < size; i++) {
                        String w = q.poll();
                        List<String> nextWords = nextWords(w, wordSet);
                        graph.get(w).addAll(nextWords);
                        for (String next : nextWords) {
                              if (!dMap.containsKey(next)) {
                                    q.offer(next);
                                    dMap.put(next, paces);
                             }
                       }
                 }
           }
     }
      private List<String> nextWords(String word, Set<String> wordSet) {
            List<String> result = new ArrayList<>();
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                  char cur = chars[i];
                  for (char c = 'a'; c <= 'z'; c++) {
                        if (c == cur) {
                              continue;
                       }
                        chars[i] = c;
                        String newString = new String(chars);
                        if (wordSet.contains(newString)) {
                              result.add(newString);
                       }
                 }
                  chars[i] = cur;
           }
            return result;
     }
      
      private void dfs(String currentWord, String endWord, Map<String, Integer> dMap, Map<String, List<String>> graph,
                              List<List<String>> result, List<String> path) {
            path.add(currentWord);
            if (currentWord.equals(endWord)) {
                  result.add(new ArrayList<>(path));
           } else {
                  for (String s : graph.get(currentWord)) {
                        if (dMap.get(currentWord) == dMap.get(s) + 1) {
                              dfs(s, endWord, dMap, graph, result, path);
                       }
                 }
           }
            path.remove(path.size() - 1);
     }
}