Word Ladder II几个地方看不太懂请教一下。。。

1. class Node {
   
2.     public int level = 1;
   
3.     public Node previous;
   
4.     public String str;
   
5.     public Node(int l, Node n, String s) {
   
6.         level = l;
   
7.         previous = n;
   
8.         str = s;
   
9.     }
   
10. }
    
11. public class Solution {
    
12.     public List<List<String>> findLadders(String start, String end, Set<String> dict) {
    
13.         HashMap<String,HashSet<String>> neighbours = new HashMap<String,HashSet<String>>();
    
14.         dict.add(start);
    
15.         dict.add(end);
    
16.         for(String str : dict)
    
17.             buildGraph(neighbours, str, dict);
    
18.         List<List<String>> res = new ArrayList<List<String>>();
    
19.         LinkedList<Node> queue = new LinkedList<Node>();
    
20.         queue.add(new Node(1, null, start));
    
21.         int previousLevel = 0;
    
22.         HashMap<String,Integer> visited = new HashMap<String,Integer>();
    
23.         while(!queue.isEmpty()) {
    
24.             Node n = queue.poll();
    
25.             if(end.equals(n.str)) {
    
26.                 if(previousLevel ==0 || n.level == previousLevel) {
    
27.                     previousLevel = n.level;
    
28.                     findPath(n, res);
    
29.                 }
    
30.                 else
    
31.                     break;
    
32.             } else {
    
33.                 HashSet<String> set = neighbours.get(n.str);
    
34.                 if(set == null || set.isEmpty())
    
35.                     continue;
    
36.               //  ArrayList<String> toRemove = new ArrayList<String>();
    
37.                 for(String s: set) {
    
38.                     if(visited.containsKey(s)) {
    
39.                     int occurLevel = visited.get(s);
    
40.                     if(n.level+1 > occurLevel) {
    
41.                         neighbours.get(s).remove(n.str);
    
42.                      //   toRemove.add(s);
    
43.                         continue;
    
44.                     }
    
45.                     }
    
46.                     visited.put(s, n.level + 1);
    
47.                     queue.add(new Node(n.level + 1, n, s));
    
48.                     if(neighbours.containsKey(s))
    
49.                         neighbours.get(s).remove(n.str);
    
50.                 }
    
51.                 //for(String s: toRemove) {
    
52.                   //  set.remove(s);
    
53.                // }
    
54.             }
    
55.         }
    
56.         return res;
    
57.     }
    
58.     public void buildGraph(HashMap<String,HashSet<String>> neighbours, String str, Set<String> dict) {
    
59.        // int level = 1, next = 0, cur = 1;
    
60.         int len = str.length();
    
61.         char[] wordUnit = str.toCharArray();
    
62.         for(int i = 0; i < len; i++) {
    
63.             char c = wordUnit[i];
    
64.             for(char j = 'a'; j <='z'; j++) {
    
65.                 if(c == j)   //跑到和自身相同的字符串跳过去！
    
66.                     continue;
    
67.                 wordUnit[i] = j;
    
68.                 String newstr = new String(wordUnit);
    
69.                 if(dict.contains(newstr)) {
    
70.                     HashSet<String> set = neighbours.get(str);
    
71.                     if(set != null)
    
72.                         set.add(newstr);
    
73.                     else {
    
74.                         HashSet<String> newset = new HashSet<String>();
    
75.                         newset.add(newstr);
    
76.                         neighbours.put(str,newset);
    
77.                     }
    
78.                 }
    
79.             }
    
80.             wordUnit[i] = c;
    
81.         }
    
82.     }
    
83.     public void findPath(Node n, List<List<String>> result) {
    
84.         ArrayList<String> path = new ArrayList<String>();
    
85.         Node p = n;
    
86.         while(p != null) {
    
87.             path.add(0, p.str);
    
88.             p = p.previous;
    
89.         }
    
90.         result.add(path);
    
91.     }
    
92. }

复制代码

FindLadders中的if(previousLevel ==0 || n.level == previousLevel) {
                    previousLevel = n.level;
                    findPath(n, res);
                }和if(n.level+1 > occurLevel) {
                        neighbours.get(s).remove(n.str);是在判断什么哦。。。谢谢了！

这算是一个比较繁琐的BFS题 而且我觉得这个代码写得稍微有点复杂。。这几句我也没太看懂。。就稍微说说我对这题的理解。 这题跟word ladder I的不同就在于，在I题中每一次BFS的时候如果一个word1变化出的所有其他word2中有已经出现过的就直接忽略 因为我们要找的是最短的ladder的长度所以不能走回头路。而word ladderII要找出所有的path，那就意味着如果在某一层word1变化出的word2们中如果有已经出现过的，这时候不能直接丢掉，而是要检查如果这个重复出现的word2正好已经出现在了word1的下一层中 那么假设是某个word3在word1的同层中向下变化出了word2 那么从最开始的word到word2的变化path就是从原始词word经word1和word3变化到word2的path的并集

FindLadders中的if(previousLevel ==0 || n.level == previousLevel)  {...}到达最后一个单词的时候要检查是否把这个path放进结果中，如果x步找到了最后一个单词， 那x+1步才找到单词的path就不要放进结果中了。因为最外面的大while loop的condition是!queue.empty()，没办法及时终止，所以他查level来判断当前还是不是最短path。 previousLevel==0 则对应的是第一次找到path的情况。

if(n.level+1 > occurLevel)        neighbours.get(s).remove(n.str);
这个就是看如果这个单词在这轮之前已经visit过了，那就删掉，因为如果在后一轮又visit同一个单词那一定是比最快路线慢了一步。


我也觉得这个code整体写复杂了，有更简洁的写法。 另外一开始建Neighbors我也觉得没必要，况且字典可能很大，不如直接查当前单词换一个字母是否在字典里快。