Word Ladder II

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 intermediate word must exist in the word list

For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Return
1. [
2. ["hit","hot","dot","dog","cog"],
3. ["hit","hot","lot","log","cog"]
4. ]

Note:
* All words have the same length.
* All words contain only lowercase alphabetic characters.

Solution:
1. public class Solution {
2. public List<List> findLadders(String start, String end, Set dict) {
3. // hash set for both ends
4. Set set1 = new HashSet();
5. Set set2 = new HashSet();
6. 7. // initial words in both ends
8. set1.add(start);
9. set2.add(end);
10. 11. // we use a map to help construct the final result
12. Map<String, List> map = new HashMap<String, List>();
13. 14. // build the map
15. helper(dict, set1, set2, map, false);
16. 17. List<List> res = new ArrayList<List>();
18. List sol = new ArrayList(Arrays.asList(start));
19. 20. // recursively build the final result
21. generateList(start, end, map, sol, res);
22. 23. return res;
24. }
25. 26. boolean helper(Set dict, Set set1, Set set2, Map<String, List> map, boolean flip) {
27. if (set1.isEmpty()) {
28. return false;
29. }
30. 31. if (set1.size() > set2.size()) {
32. return helper(dict, set2, set1, map, !flip);
33. }
34. 35. // remove words on current both ends from the dict
36. dict.removeAll(set1);
37. dict.removeAll(set2);
38. 39. // as we only need the shortest paths
40. // we use a boolean value help early termination
41. boolean done = false;
42. 43. // set for the next level
44. Set set = new HashSet();
45. 46. // for each string in end 1
47. for (String str : set1) {
48. for (int i = 0; i < str.length(); i++) {
49. char[] chars = str.toCharArray();
50. 51. // change one character for every position
52. for (char ch = 'a'; ch <= 'z'; ch++) {
53. chars[i] = ch;
54. 55. String word = new String(chars);
56. 57. // make sure we construct the tree in the correct direction
58. String key = flip ? word : str;
59. String val = flip ? str : word;
60. 61. List list = map.containsKey(key) ? map.get(key) : new ArrayList();
62. 63. if (set2.contains(word)) {
64. done = true;
65. 66. list.add(val);
67. map.put(key, list);
68. }
69. 70. if (dict.contains(word)) {
71. set.add(word);
72. 73. list.add(val);
74. map.put(key, list);
75. }
76. }
77. }
78. }
79. 80. // early terminate if done is true
81. return done || helper(dict, set2, set, map, !flip);
82. }
83. 84. void generateList(String start, String end, Map<String, List> map, List sol, List<List> res) {
85. if (start.equals(end)) {
86. res.add(new ArrayList(sol));
87. return;
88. }
89. 90. // need this check in case the diff between start and end happens to be one
91. // e.g "a", "c", {"a", "b", "c"}
92. if (!map.containsKey(start)) {
93. return;
94. }
95. 96. for (String word : map.get(start)) {
97. sol.add(word);
98. generateList(word, end, map, sol, res);
99. sol.remove(sol.size() - 1);
100. }
101. }
102. }