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

ac时间是700ms左右，大致思路就是采用合适的数据结构和比较差一个字符的方法，然后bfs建图，随后dfs找出所有起点到终点路径就是了。
class Solution {
public:

    unordered_multimap<string, string> path_map;
    vector<vector<string> > res;
    unordered_set<string> visited;

    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        dict.insert(start);
        dict.insert(end);
        dict.erase(start);
        path_map.clear();

        unordered_set<string> last_layer, curr_layer;
        curr_layer.insert(start);
        
        //bool to_break = false;
        while (!last_layer.empty() || !curr_layer.empty())
        {

            for (unordered_set<string>::iterator cit = last_layer.begin(); cit != last_layer.end(); ++cit)
            {
                dict.erase(*cit);
            }
            last_layer.clear();
            
            for (unordered_set<string>::iterator cit = curr_layer.begin(); cit != curr_layer.end(); ++cit)
            {
                string cur = *cit;

                /*if (cur == end)
                {
                    to_break = true;
                    break;
                }*/

                for (int i = 0; i < cur.size(); ++i)
                {
                    string handle_str = cur;
                    int stop = handle_str[i] - 'a';
               
                    for (int j = (stop+1)%26; j != stop; j = (j+1)%26)
                    {
                        handle_str[i] = 'a' + j;
                    
                        if (dict.find(handle_str) != dict.end())
                        {
                            last_layer.insert(handle_str);
                            path_map.insert(pair<string, string>(handle_str, cur));
                        }
                    }
                }
            }
            
            if (last_layer.count(end))
                break;
            //if (to_break)
            //    break;
            curr_layer = last_layer;
        }
        
        vector<string> path;
        //for (unordered_multimap<string, string>::iterator cit = path_map.begin(); cit != path_map.end(); ++cit)
        //    visited[*cit] = false;
        if (!path_map.empty())
            get_path(end, start, path);
        return res;
    }
   
    void get_path(string curr, string start, vector<string> path)
    {
        if (curr == start)
        {
            path.insert(path.begin(), start);
            res.push_back(path);
            //path.clear();
            return;
        }
        
        unordered_multimap<string, string>::iterator it;

        pair<unordered_multimap<string, string>::iterator, unordered_multimap<string, string>::iterator> itrangexx = path_map.equal_range(curr);
        it = itrangexx.first;
        while (true)
        {            
            path.insert(path.begin(), curr);

            if (it != path_map.end() && it != itrangexx.second && visited.find(it->second) != visited.end())
            {   
                ++it;
            
            }
            
            if (it == itrangexx.second || it == path_map.end())
                break;
            else
            {
                string prev;

                prev = it->second;
                //path_map.erase(it);
                visited.insert(prev);
               
                get_path(prev, start, path);
               
                visited.erase(prev);
                if (!path.empty())
                    path.erase(path.begin());
            }
            ++it;
        }
    }
};

这题就看出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

复制代码

1. public class Solution {
   
2.     public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
   
3.     // Start typing your Java solution below
   
4.     // DO NOT write main() function
   
5.     // method would be similar, except that, we need to store the path
   
6.     // in addition, if we get the result, we didn't stop until we finish
   
7.     // all the path of the same length
   
8.     // visited map the string to the list of its ancestor
   
9.     HashMap<String, HashSet<String>> visited=new HashMap<String, HashSet<String>>();
   
10.     HashMap<String, Integer> level=new HashMap<String, Integer>();
    
11.     LinkedList<String> queue=new LinkedList<String>();
    
12.     ArrayList<ArrayList<String>> result=new ArrayList<ArrayList<String>>();
    
13.     if (start==null || end==null || start.length()!=end.length())
    
14.     {
    
15.         return result;
    
16.     }
    
17.     // we also need to store the path for the start
    
18.     HashSet<String> path=new HashSet<String>();
    
19.     // we record the minimal length we get
    
20.     int min_length=Integer.MAX_VALUE;
    
21.     visited.put(start, path);
    
22.     level.put(start, 1);
    
23.     queue.add(start);
    
24.     while(!queue.isEmpty())
    
25.     {
    
26.         String s=queue.remove();
    
27.         char[] chars=s.toCharArray();
    
28.         for (int i=0; i<s.length(); i++)
    
29.         {
    
30.             char old=chars[i];
    
31.             for (char c='a'; c<='z'; c++)
    
32.             {
    
33.                 chars[i]=c;
    
34.                 String s2=new String(chars);
    
35.                 // avoid circle
    
36.                 // check whether it is in the dictionary
    
37.                 // we only add the string which is nearer to the start
    
38.                 if (dict.contains(s2) && (!level.containsKey(s2) || (level.containsKey(s2) && level.get(s2)>level.get(s))))
    
39.                 {
    
40.                     // we update the ancestor of the string
    
41.                     if (visited.containsKey(s2))
    
42.                     {
    
43.                         visited.get(s2).add(s);
    
44.                     }
    
45.                     else
    
46.                     {
    
47.                         // we haven't seen this node before
    
48.                         // thus we add it to the queue and also its ancestor
    
49.                         path=new HashSet<String>();
    
50.                         path.add(s);
    
51.                         visited.put(s2, path);
    
52.                         level.put(s2, level.get(s)+1);
    
53.                         queue.add(s2);
    
54.                     }
    
55.                 }
    
56.                 if (s2.equals(end))
    
57.                 {
    
58.                     // we found it
    
59.                     // we will use back trace to found its path to start
    
60.                     if (level.get(s)<min_length)
    
61.                     {
    
62.                         // it is shortest path
    
63.                         ArrayList<String> entry=new ArrayList<String>();
    
64.                         entry.add(end);
    
65.                         result.addAll(back_trace(s, visited, entry));
    
66.                         min_length=level.get(s)+1;
    
67.                     }
    
68.                     else
    
69.                     {
    
70.                         // ok, all the remaining path should be longer
    
71.                         break;
    
72.                     }
    
73.                 }
    
74.             }
    
75.             chars[i]=old;
    
76.         }
    
77.     }
    
78.     return result;
    
79. }
    
80. 
    
81. private ArrayList<ArrayList<String>> back_trace(String end, HashMap<String, HashSet<String>> visited, ArrayList<String> path)
    
82. {
    
83.     ArrayList<ArrayList<String>> result=new ArrayList<ArrayList<String>>();
    
84.     ArrayList<String> entry=new ArrayList<String>(path);
    
85.     entry.add(0, end);
    
86.     if (visited.get(end).size()<1)
    
87.     {
    
88.         result.add(entry);
    
89.         return result;
    
90.     }
    
91.     for (String str: visited.get(end))
    
92.     {
    
93.         result.addAll(back_trace(str, visited, entry));
    
94.     }
    
95.     return result;
    
96. }
    
97. }

复制代码

看了好多解法，还是觉得这个思路最为清晰

同样思路，c++能过，java就不行

applepie11 发表于 2014-11-29 01:52
同样思路，c++能过，java就不行

因为cpp总是比java跑起来快。
lc是根据运行时间来卡的

谢谢 参考了

给个小建议，用双向BFS搜索，实现麻烦一点，但是效率高一些

这个题目真的是难啊～

贴一个我的，感觉比较方便记忆和简洁，易读性好：
避免了adjacent list，也避免了前驱节点。
用的有两点：
1 先走一遍bfs，用一个HashMap记录dict里的每一个词到start的距离
2 再来一遍dfs，找到所有的解
注意dfs时，要把start和end的位置颠倒一下，因为oj的数据是前密后疏的

1.     public static List<List<String>> findLadders(String start, String end, Set<String> dict) {
   
2.         List<List<String>> ret = new ArrayList<>();
   
3.         List<String> seq = new ArrayList<>();
   
4. 
   
5.         HashMap<String,Integer> path = new HashMap<>();
   
6.         bfs(start, end, dict, path);
   
7.         dfs(ret, seq, end, start, dict, path);
   
8. 
   
9.         for(List<String> l : ret)   l.add(end);
   
10.         return ret;
    
11.     }
    
12. 
    
13.     private static void bfs(String start, String end, Set<String> dict, HashMap<String,Integer> path) {
    
14.         Queue<String> queue = new LinkedList<>();
    
15.         queue.add(start);
    
16.         path.put(start, 0);
    
17. 
    
18.         while(!queue.isEmpty()) {
    
19.             String cur = queue.remove();
    
20. 
    
21.             for(int i=0; i<start.length(); i++) {
    
22.                 char[] cc = cur.toCharArray();
    
23.                 for(char c='a'; c<='z'; c++) {
    
24.                     if(c == cur.charAt(i)) continue;
    
25.                     cc[i] = c;
    
26.                     String next = new String(cc);
    
27.                     if(dict.contains(next) || next.equals(end)) {
    
28.                         if(!path.containsKey(next)) {
    
29.                             path.put(next, path.get(cur)+1);
    
30.                             queue.add(next);
    
31.                         }
    
32.                     }
    
33.                 }
    
34.             }
    
35.         }
    
36.     }
    
37. 
    
38.     private static void dfs(List<List<String>> ret, List<String> seq, String start, String end,
    
39.                              Set<String> dict, HashMap<String,Integer> path) {
    
40.         if(start.equals(end)) {
    
41.             List<String> newSeq = new ArrayList<>(seq);
    
42.             Collections.reverse(newSeq);
    
43.             ret.add(newSeq);
    
44.             return;
    
45.         }
    
46.         if(!path.containsKey(start))    return;
    
47. 
    
48.         for(int i=0; i<start.length(); i++) {
    
49.             char[] cc = start.toCharArray();
    
50.             for(char c='a'; c<='z'; c++) {
    
51.                 if(c == start.charAt(i)) continue;
    
52.                 cc[i] = c;
    
53.                 String next = new String(cc);
    
54.                 if(dict.contains(next) && path.get(next) == path.get(start)-1 || next.equals(end)) {
    
55.                     seq.add(next);
    
56.                     dfs(ret, seq, next, end, dict, path);
    
57.                     seq.remove(next);
    
58.                 }
    
59.             }
    
60.         }
    
61.     }

复制代码

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

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

最后见到end word就收
完成