Word Ladder II

 1 public class Solution {
 2     public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
 3         List<List<String>> res = new LinkedList<List<String>>();
 4         Map<String, Integer> visited = new HashMap<>();
 5         Queue<Node> queue = new LinkedList<>();
 6         List<Node> nodeList = new LinkedList<Node>();
 7         visited.put(beginWord, 0);
 8         queue.offer(new Node(beginWord));
 9         int lastCnt = 1;
10         int currCnt = 0;
11         int level = 1;
12         boolean foundEndWord = false;
13 
14         while(!queue.isEmpty()) {
15             Node currNode = queue.poll();
16             StringBuilder wordBuff = new StringBuilder(currNode.word);
17             lastCnt--;
18             for(int i = 0; i < wordBuff.length(); i++) {
19                 char currChar = wordBuff.charAt(i);
20                 for(char c = 'a'; c <= 'z'; c++) {
21                     if(c == currChar) {
22                         continue;
23                     }
24 
25                     wordBuff.setCharAt(i, c);
26                     String tmpWord = wordBuff.toString();
27                     Node tmpNode = new Node(tmpWord, currNode);
28 
29                     if(endWord.equals(tmpWord)) {
30                         nodeList.add(tmpNode);
31                         foundEndWord = true;
32                     }
33 
34                     if(wordList.contains(tmpWord)) {
35                         if(visited.containsKey(tmpWord) && visited.get(tmpWord)<level) {
36                             continue;
37                         }
38                         currCnt++;
39                         queue.offer(tmpNode);
40                         visited.put(tmpWord, level);
41                     }
42                 }
43                 wordBuff.setCharAt(i, currChar);
44             }
45 
46             if(lastCnt == 0) {
47                 if(foundEndWord) {
48                     break;
49                 }
50                 lastCnt = currCnt;
51                 currCnt = 0;
52                 level++;
53             }
54         }
55 
56         for(Node currNode: nodeList) {
57             List<String> list = new LinkedList<>();
58             list.add(currNode.word);
59             while(currNode.parent != null) {
60                 list.add(0, currNode.parent.word);
61                 currNode = currNode.parent;
62             }
63             res.add(list);
64         }
65 
66         return res;
67     }
68 
69     class Node {
70         Node parent;
71         String word;
72 
73         public Node(String word){
74             this.word = word;
75         }
76 
77         public Node(String word, Node parent) {
78             this.word = word;
79             this.parent = parent;
80         }
81     }
82 }