1
class Solution {
2
  public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
3
    Set<String> dict = new HashSet(wordList);
4
    if (!dict.contains(endWord)) return new ArrayList();
5

6
    // adjacent words for each word
7
    Map<String, List<String>> adjacency = new HashMap();
8
    Queue<String> queue = new LinkedList();
9
    // does path exist?
10
    boolean found = false;
11

12
    // BFS for shortest path, keep removing visited words
13
    queue.offer(beginWord);
14
    dict.remove(beginWord);
15

16
    while (!found && !queue.isEmpty()) {
17
      int size = queue.size();
18
      // adjacent words in current level
19
      HashSet<String> explored = new HashSet();
20

21
      while (size-- > 0) {
22
        String word = queue.poll();
23

24
        if (adjacency.containsKey(word)) continue;
25

26
        // remove current word from dict, and search for adjacent words
27
        dict.remove(word);
28
        List<String> adjacents = getAdjacents(word, dict);
29
        adjacency.put(word, adjacents);
30

31
        for (String adj : adjacents) {
32
          if (!found && adj.equals(endWord)) found = true;
33

34
          explored.add(adj);
35
          queue.offer(adj);
36
        }
37
      }
38
      // remove words explored in current level from dict
39
      for (String word : explored) dict.remove(word);
40
    }
41

42
    // if a path exist, dfs to find all the paths
43
    if (found) return dfs(beginWord, endWord, adjacency, new HashMap());
44
    else return new ArrayList();
45
  }
46

47
  private List<String> getAdjacents(String word, Set<String> dict) {
48
    List<String> adjs = new ArrayList();
49
    char[] wordChars = word.toCharArray();
50

51
    for (int i = 0; i < wordChars.length; i++)
52
      for (char c = 'a'; c <= 'z'; c++) {
53
        char temp = wordChars[i];
54
        wordChars[i] = c;
55

56
        String newAdj = new String(wordChars);
57
        if (dict.contains(newAdj)) adjs.add(newAdj);
58

59
        wordChars[i] = temp;
60
      }
61
    return adjs;
62
  }
63

64
  private List<List<String>> dfs(
65
      String src,
66
      String dest,
67
      Map<String, List<String>> adjacency,
68
      Map<String, List<List<String>>> memo) {
69
    if (memo.containsKey(src)) return memo.get(src);
70

71
    List<List<String>> paths = new ArrayList();
72

73
    // reached dest? return list with dest word
74
    if (src.equals(dest)) {
75
      paths.add(
76
          new ArrayList() {
77
            {
78
              add(dest);
79
            }
80
          });
81
      return paths;
82
    }
83

84
    // no adjacent for curr word? return empty list
85
    List<String> adjacents = adjacency.get(src);
86
    if (adjacents == null || adjacents.isEmpty()) return paths;
87

88
    for (String adj : adjacents) {
89
      List<List<String>> adjPaths = dfs(adj, dest, adjacency, memo);
90

91
      for (List<String> path : adjPaths) {
92
        if (path.isEmpty()) continue;
93

94
        List<String> newPath =
95
            new ArrayList() {
96
              {
97
                add(src);
98
              }
99
            };
100
        newPath.addAll(path);
101

102
        paths.add(newPath);
103
      }
104
    }
105
    memo.put(src, paths);
106
    return paths;
107
  }
108
}