有人做过leetcode里的word ladder II 吗？

这题目实在是太适合python了  如此简洁

就是基本的bfs，典型的level order traverse
有两个坑：
1. 不要判断字典里的某两个word是否只相差一个字母，而是要判断某个word的邻居（和他只相差一个字母的所有word）是否在字典里，这样的改进会使这一步的复杂度下降了很多，否则超时妥妥
2. 记录每一层已经访问过的word，一层结束后把他们加到大的visited里面，记住每次要访问的word不可以是在visited里面的

最后见到end word就收
完成

2015fallcser 发表于 2015-5-24 12:46
这题目实在是太适合python了  如此简洁

就是基本的bfs，典型的level order traverse

感觉这个是会超时的...

sevensevens 发表于 2015-11-10 14:56
感觉这个是会超时的...

并不会 紫薯紫薯紫薯

2015fallcser 发表于 2015-11-10 15:05
并不会 紫薯紫薯紫薯

我之前用那个思路写的会超时...垅主方便share一下code么

只要用bfs就够了

1. public class Solution {
   
2.     public List<List<String>> findLadders(String begin, String end, Set<String> dict) {
   
3.         List<List<String>> ret = new ArrayList<>();
   
4.         Queue<Item> queue = new LinkedList<>();
   
5.         Item first = new Item(begin, 1);
   
6.         queue.add(first);
   
7.         first.list.add(begin);
   
8.         
   
9.         Set<String> visited = new HashSet<>();
   
10.         
    
11.         int min = Integer.MAX_VALUE;
    
12.         int preSteps = 0;
    
13.         while (!queue.isEmpty()) {
    
14.             Item cur = queue.poll();
    
15.             if (cur.s.equals(end)) {
    
16.                 if (cur.n <= min) {
    
17.                     min = cur.n;
    
18.                     ret.add(cur.list);
    
19.                 }
    
20.             }
    
21.             if (cur.n > min)    break;
    
22.             if (cur.n > preSteps)   dict.removeAll(visited);
    
23.             preSteps = cur.n;
    
24.             
    
25.             char[] cc = cur.s.toCharArray();
    
26.             for (int i=0; i<cc.length; i++) {
    
27.                 char old = cc[i];
    
28.                 for (char j='a'; j<='z'; j++) {
    
29.                     cc[i] = j;
    
30.                     String newS = new String(cc);
    
31.                     if (cur.s.equals(newS) || !dict.contains(newS)) continue;
    
32.                     visited.add(newS);
    
33.                     Item newItem = new Item(newS, cur.n+1);
    
34.                     newItem.list.addAll(cur.list);
    
35.                     newItem.list.add(newS);
    
36.                     queue.add(newItem);
    
37.                 }
    
38.                 cc[i] = old;
    
39.             }
    
40.         }
    
41.         return ret;
    
42.     }
    
43.    
    
44.     class Item {
    
45.         String s;
    
46.         int n;
    
47.         List<String> list;
    
48.         public Item(String s, int n) {
    
49.             this.s = s;
    
50.             this.n = n;
    
51.             list = new ArrayList<>();
    
52.         }
    
53.     }
    
54. }

复制代码

2015fallcser 发表于 2015-5-24 12:46
这题目实在是太适合python了  如此简洁

就是基本的bfs，典型的level order traverse

真的，我没有一层一层扫，而是一个一个访问然后记录depth，这个做法正好超时一点点，就跑过来翻答案，反正Python怎么做都不会超过40行吧。。。结果看到前面那些Java的答案那么长，差点吓尿了。。。

用Trie数据结构 再DFS