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

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start toend, such that:

• Only one letter can be changed at a time
• Each intermediate word must exist in the dictionary
  

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return:

[  ["hit","hot","dot","dog","cog"],  ["hit","hot","lot","log","cog"

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.
  

自己能写的算法是先用BFS找出每个word离origin多远，然后用类似dfs把路径找出来，没过leetcode OJ的大测试，超时了，不知道有什么比较好的算法做这题？

这题就看出Python的爽的地方了

source: 我的github https://github.com/jw2013/Leetco ... rd%20Ladder%20II.py

1. class Solution:
   
2.     def backtrack(self, result, trace, path, word):
   
3.         if len(trace[word]) == 0:
   
4.             result.append([word] + path)
   
5.         else:
   
6.             for prev in trace[word]:
   
7.                 self.backtrack(result, trace, [word] + path, prev)
   
8.                
   
9.     def findLadders(self, start, end, dict):
   
10.         result, trace, current = [], {word: [] for word in dict}, set([start])
    
11.         while current and end not in current:
    
12.             for word in current:
    
13.                 dict.remove(word)
    
14.             next = set([])
    
15.             for word in current:
    
16.                 for i in range(len(word)):
    
17.                     for j in 'abcdefghijklmnopqrstuvwxyz':
    
18.                         candidate = word[:i] + j + word[i + 1:]
    
19.                         if candidate in dict:
    
20.                             trace[candidate].append(word)
    
21.                             next.add(candidate)
    
22.             current = next
    
23.         if current:
    
24.             self.backtrack(result, trace, [], end)
    
25.         return result

复制代码

iostreamin 发表于 2014-1-21 13:26
得大牛指点，Java通过。

Clear illustration.

Some advice, since it's level-ordered, line 55 & 62 can be deleted...

得大牛指点，Java通过。

1. public class Solution {
   
2.     public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
   
3.         
   
4.         // Start typing your Java solution below
   
5.         // DO NOT write main() function              
   
6.         
   
7.         HashMap<String, HashSet<String>> neighbours = new HashMap<String, HashSet<String>>();
   
8.         
   
9.         dict.add(start);
   
10.         dict.add(end);
    
11.         
    
12.         // init adjacent graph        
    
13.         for(String str : dict){
    
14.             calcNeighbours(neighbours, str, dict);
    
15.         }
    
16.         
    
17.         ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
    
18.         
    
19.         // BFS search queue
    
20.         LinkedList<Node> queue = new LinkedList<Node>();
    
21.         queue.add(new Node(null, start, 1));
    
22.         
    
23.         // BFS level
    
24.         int previousLevel = 0;
    
25.         
    
26.         // mark which nodes have been visited, to break infinite loop
    
27.         HashMap<String, Integer> visited = new HashMap<String, Integer>();
    
28.         while(!queue.isEmpty()){
    
29.             Node n = queue.pollFirst();            
    
30.             if(end.equals(n.str)){
    
31.                 // fine one path, check its length, if longer than previous path it's valid
    
32.                 // otherwise all possible short path have been found, should stop
    
33.                 if(previousLevel == 0 || n.level == previousLevel){
    
34.                     previousLevel = n.level;
    
35.                     findPath(n, result);                    
    
36.                 }else {
    
37.                     // all path with length *previousLevel* have been found
    
38.                     break;
    
39.                 }               
    
40.             }else {
    
41.                 HashSet<String> set = neighbours.get(n.str);                 
    
42.                
    
43.                 if(set == null || set.isEmpty()) continue;
    
44.                 // note: I'm not using simple for(String s: set) here. This is to avoid hashset's
    
45.                 // current modification exception.
    
46.                 ArrayList<String> toRemove = new ArrayList<String>();
    
47.                 for (String s : set) {
    
48.                     
    
49.                     // if s has been visited before at a smaller level, there is already a shorter
    
50.                     // path from start to s thus we should ignore s so as to break infinite loop; if
    
51.                     // on the same level, we still need to put it into queue.
    
52.                     if(visited.containsKey(s)){
    
53.                         Integer occurLevel = visited.get(s);
    
54.                         if(n.level+1 > occurLevel){
    
55.                             neighbours.get(s).remove(n.str);
    
56.                             toRemove.add(s);
    
57.                             continue;
    
58.                         }
    
59.                     }
    
60.                     visited.put(s,  n.level+1);
    
61.                     queue.add(new Node(n, s, n.level + 1));
    
62.                     if(neighbours.containsKey(s))
    
63.                         neighbours.get(s).remove(n.str);
    
64.                 }
    
65.                 for(String s: toRemove){
    
66.                     set.remove(s);
    
67.                 }
    
68.             }
    
69.         }
    
70. 
    
71.         return result;
    
72.     }
    
73.    
    
74.     public void findPath(Node n, ArrayList<ArrayList<String>> result){
    
75.         ArrayList<String> path = new ArrayList<String>();
    
76.         Node p = n;
    
77.         while(p != null){
    
78.             path.add(0, p.str);
    
79.             p = p.parent;
    
80.         }
    
81.         result.add(path);
    
82.     }
    
83. 
    
84.     /*
    
85.      * complexity: O(26*str.length*dict.size)=O(L*N)
    
86.      */
    
87.     void calcNeighbours(HashMap<String, HashSet<String>> neighbours, String str, HashSet<String> dict) {
    
88.         int length = str.length();
    
89.         char [] chars = str.toCharArray();
    
90.         for (int i = 0; i < length; i++) {
    
91.             
    
92.             char old = chars[i];
    
93.             for (char c = 'a'; c <= 'z'; c++) {
    
94. 
    
95.                 if (c == old)  continue;
    
96.                 chars[i] = c;
    
97.                 String newstr = new String(chars);               
    
98.                
    
99.                 if (dict.contains(newstr)) {
    
100.                     HashSet<String> set = neighbours.get(str);
     
101.                     if (set != null) {
     
102.                         set.add(newstr);
     
103.                     } else {
     
104.                         HashSet<String> newset = new HashSet<String>();
     
105.                         newset.add(newstr);
     
106.                         neighbours.put(str, newset);
     
107.                     }
     
108.                 }               
     
109.             }
     
110.             chars[i] = old;
     
111.         }
     
112.     }
     
113.    
     
114.     private class Node {
     
115.         public Node parent;
     
116.         public String str;
     
117.         public int level;
     
118.         public Node(Node p, String s, int l){
     
119.             parent = p;
     
120.             str = s;
     
121.             level = l;
     
122.         }
     
123.     }
     
124. }

复制代码

没做过，随便谈谈自己想法。把dictionary按照是否相连做个图，o(n^2） 然后把start和dictionary中每个只差一个字母的连条边,o(n)，end也如此连若干条边 o(n)。
然后BFS？ o(m+n)

不知有没有优化了楼主的算法。

我觉得这题很坑的。。。关键在于一开始，要建立一个图，看dict中任意两个单词是否只差一个字母
用O(n^2)的好像就会超时，于是只能对每个单词，枚举与它只有一个字母不同的所有单词，看是否在dict里，这样就是26*l (单词长度) * n * 查dict的时间(认为是常数吧)

大数据应该就能过了。基本算法同LS

careercup上也有 貌似

因为是问最短路径所以是这里dfs不合适 用bfs
然后是怎么判断next step. 同时需要用HashMap来记录走过的路径 当遇到最短路径的时候根据最后一个词 重建整个路径

贴一个java 代码 应该可以过test large

1. public ArrayList<ArrayList<String>> test(String start, String end, HashSet<String> dict) {
   
2.     HashMap<String, ArrayList<String>> path = new HashMap<String, ArrayList<String>>();
   
3.     HashMap<String, ArrayList<String>> tmpPath = new HashMap<String, ArrayList<String>>();
   
4.     Queue<String> curLevel = new LinkedList<String>();
   
5.     Queue<String> nextLevel = new LinkedList<String>();
   
6.     curLevel.add(start);
   
7.     boolean isShortestLevel = false;
   
8.     while (!curLevel.isEmpty()) {
   
9.         String str = curLevel.remove();
   
10.         for (int i = 0; i < start.length(); ++i) {
    
11.             for(char j = 'a'; j <= 'z'; ++j){
    
12.                 // Change the str then check if the dict contains it.
    
13.                 char[] chs = str.toCharArray();
    
14.                 chs[i] = j;
    
15.                 String oneCharDiff = new String(chs);
    
16.                 if (oneCharDiff.equals(str)) {
    
17.                     continue;
    
18.                 }
    
19.                 if (oneCharDiff.equals(end)) {
    
20.                     isShortestLevel = true; // Reach the shortest path.
    
21.                 }
    
22.                 if (!path.containsKey(oneCharDiff) && dict.contains(oneCharDiff)) {
    
23.                     if (!tmpPath.containsKey(oneCharDiff)) {
    
24.                         ArrayList<String> arr = new ArrayList<String>();
    
25.                         arr.add(str);
    
26.                         tmpPath.put(oneCharDiff, arr);
    
27.                         nextLevel.add(oneCharDiff);
    
28.                     } else {
    
29.                         ArrayList<String> arr = tmpPath.get(oneCharDiff);
    
30.                         arr.add(str);
    
31.                         tmpPath.put(oneCharDiff, arr);
    
32.                     }
    
33.                 }
    
34.             }
    
35.         }
    
36.         if (curLevel.isEmpty()) {
    
37.             Queue<String> tmp = nextLevel; // Swap nextLevel and curLevel.
    
38.             nextLevel = curLevel;
    
39.             curLevel = tmp;
    
40.             path.putAll(tmpPath); // Move all paths hashed as this level to global path map.
    
41.             tmpPath = new HashMap<String, ArrayList<String>>(); // tmpPath.clear()
    
42.             if (isShortestLevel) {
    
43.                 return dfsPath(path, start, end); // Finished with level with shortest path. Start reconstructing path.
    
44.             }
    
45.         }
    
46.     }
    
47.     return new ArrayList<ArrayList<String>>();
    
48. }
    
49. public ArrayList<ArrayList<String>> dfsPath(HashMap<String, ArrayList<String>> path, String start, String end) {
    
50.     // Standord DFS.
    
51.     ArrayList<ArrayList<String>> all = new ArrayList<ArrayList<String>>();
    
52.     ArrayList<String> one = new ArrayList<String>();
    
53.     one.add(start);
    
54.     nextPath(path, start, end, all, one, 0);
    
55.     for (ArrayList<String> i : all) System.out.println(i);
    
56.     return all;
    
57. }

复制代码

xiaoyangmie 发表于 2013-2-25 15:53
我觉得这题很坑的。。。关键在于一开始，要建立一个图，看dict中任意两个单词是否只差一个字母
用O(n^2)的 ...

实现了一下，大数据还是木有过。肿么回事~

zxyviopond 发表于 2013-3-9 02:20
实现了一下，大数据还是木有过。肿么回事~

啊？不应该啊，那你是如何保存还有输出所有结果的呢？

xiaoyangmie 发表于 2013-3-13 08:32
啊？不应该啊，那你是如何保存还有输出所有结果的呢？

BFS 记录parentnode，找到之后反上去。

zxyviopond 发表于 2013-3-12 23:16
BFS 记录parentnode，找到之后反上去。

这个。。。要不发下代码？

我也是用BFS做了，小数据过了，大数据没过。不知道楼主最后怎么解决的？