Word Ladder II --- 一点小想法

https://discuss.leetcode.com/top ... -that-accpted-by-oj

这个是用BFS + DFS 两轮来做的，最坏情况必定是指数时间， 我想到一些加速的方法：

1.剪枝， 用memoize的方法把BFS中得到的层数位置存储下来，然后在DFS时如果遇到“层数不对”的情况就立即中断返回；

2.分块进行，从“搜索所有邻居”变为“搜索下一个邻居”， 这样可以减少分支数；
通过区别"forward edge" "backward edge" / "cross edge" ，然后只对forward edge 进行搜索

1. public class Solution {
   
2.         Set<String> unvisited;
   
3.         Map<String, List<String>> neighborMap = new HashMap<>();
   
4.         Map<String, Integer> layerMap = new HashMap<>();
   
5.         LinkedList<String> queue = new LinkedList<String>();
   
6.     public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
   
7.         List<List<String>> results = new ArrayList<>();
   
8.         // if beginWord is equal to endWord
   
9.         if (beginWord.equals(endWord)) {
   
10.                 ArrayList<String> list = new ArrayList<>();
    
11.                 list.add(beginWord);
    
12.                 results.add(list);
    
13.                 return results;
    
14.         }
    
15.         
    
16.         unvisited = new HashSet<String>(wordList);
    
17.         unvisited.add(endWord);
    
18.         unvisited.add(beginWord);
    
19. 
    
20.         queue.offer(beginWord);
    
21.         int layers = BFS(beginWord, endWord, wordList);  // first compute the min words in between;
    
22.         layerMap.put(endWord, layers + 1);
    
23.         //reinitialize
    
24.         unvisited = new HashSet<String>(wordList);
    
25.         unvisited.add(endWord);
    
26.         unvisited.remove(beginWord);   // add the first one into stack
    
27.         List<String> stack = new ArrayList<>();  
    
28.         stack.add(beginWord);
    
29.         DFS(results, beginWord, endWord, wordList, layers, stack);
    
30.         return results;
    
31.     }
    
32. 
    
33.     private void DFS(List<List<String>> results, String beginWord, String endWord, Set<String> wordList, int layers, List<String> stack) {
    
34.                 String string = stack.get(stack.size() - 1);
    
35.                 if (stack.size() == layers + 1) {
    
36.                         if (string.equals(endWord)) {
    
37.                                 results.add(new ArrayList<>(stack));
    
38.                         }
    
39.                         return;
    
40.                 }
    
41.                 // explore all of its neighbors;
    
42.                 for (String neighbor : neighborMap.get(string)) {
    
43.                         if (layerMap.get(neighbor) == null || layerMap.get(neighbor) != layerMap.get(string) + 1)
    
44.                                 continue;
    
45.                         unvisited.remove(neighbor);
    
46.                         stack.add(neighbor);
    
47.                         DFS(results, beginWord, endWord, wordList, layers, stack);
    
48.                         unvisited.add(neighbor);
    
49.                         stack.remove(stack.size() - 1);
    
50.                 }
    
51.         }
    
52. 
    
53.         private int BFS(String beginWord, String endWord, Set<String> wordList) {
    
54.                 int mediateWords = 0;
    
55.                 while (!queue.isEmpty()) {
    
56.                         mediateWords++;
    
57.                         boolean flag = false;
    
58.                         int size = queue.size();
    
59.                         for (int i = 0; i < size; ++i) {
    
60.                                 String thisString = queue.poll();
    
61.                                 unvisited.remove(thisString);
    
62.                                 queue.offer(thisString);
    
63.                         }
    
64.                         for (int i = 0; i < size; ++i) {
    
65.                                 
    
66.                                 String nextString = queue.poll();
    
67.                                 layerMap.put(nextString, mediateWords);
    
68.                                 List<String> neighborsOfNextString = findNeighbors(nextString);
    
69.                                 neighborMap.put(nextString, neighborsOfNextString);
    
70.                                 for (String string : neighborMap.get(nextString))
    
71.                                 {
    
72.                                         queue.offer(string);
    
73.                                         if (string.equals(endWord))
    
74.                                                 flag = true;
    
75.                                 }
    
76. 
    
77.                         }
    
78.                         if (flag)
    
79.                                 return mediateWords;
    
80.                 }
    
81.                 return -1;
    
82.         }
    
83. 
    
84.         // find all neighbors in unvisited set of this originString
    
85.     private List<String> findNeighbors(String originString) {
    
86.             int length = originString.length();
    
87.             char[] charArray = originString.toCharArray();
    
88.             List<String> neighbors = new ArrayList<>();
    
89.             for (int i = 0; i < length; ++i) {
    
90.                     char c = charArray[i];
    
91.                     for (int j = 0; j < 26; ++j) {
    
92.                             charArray[i] = (char)('a' + j);
    
93.                             if (unvisited.contains(String.valueOf(charArray)) && (charArray[i] != c)) {
    
94.                                     neighbors.add(String.valueOf(charArray));
    
95.                             }
    
96.                             //System.out.println(charArray[i]);
    
97.                     }
    
98.                     charArray[i] = c;
    
99.             }
    
100.             return neighbors;
     
101.     }
     
102.         public static void main(String[] args) {
     
103.             String beginWord = "a";
     
104.             String endWord = "c";
     
105.             Set<String> wordList = new HashSet<String>(Arrays.asList("a","b","c"));
     
106.             Solution solution = new Solution();
     
107.             List<List<String>> lists = solution.findLadders(beginWord, endWord, wordList);
     
108.             for (List<String> list : lists ) {
     
109.                     System.out.println(Arrays.toString(list.toArray()));
     
110.             }
     
111.             
     
112. //            for (String string : solution.findNeighbors(beginWord, wordList)) {
     
113. //                    System.out.println(string);
     
114. //            };
     
115.     }
     
116. }

复制代码