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

ArtemisYY 发表于 2013-8-27 10:14
我也是用BFS做了，小数据过了，大数据没过。不知道楼主最后怎么解决的？

用n*length*26生成adjacent list

刚刚通过这道题~做法是用BFS，然后记录下每个点前驱的点的集合，回溯找到所有的答案。一开始也是超时，主要是如何构图的问题。

首先不能用Adjacency matrix，O(n^2)超时。考虑用Adjacency List，我的做法是每个词去掉第i位后，存在Hashtable里面。然后直接查找Hashtable就能建出Adjacency List，注意这里i要从0到string的length - 1循环一遍。

图建好了，就是正常的BFS，存下每个点的所有前驱，最后回溯即可。

我刚才做完这题，但是通过的原因比较……侥幸。
一开始建立图的时候，采取了map<string, unordered_set<string> >，结果在大输入的时候超时。
接下来改成了unordered_map<string, unordered_set<string> >，就通过了。
因为map是基于树实现的，而unordered_map是基于哈希表的，一般情况下时间复杂度分别是O(n logn)和O(1)
话说，unordered_map应该是c++0x的新功能吧，Leetcode默认是包含这个头文件的，所以我觉得如果我只是map换成了unordered_map就通过的话应该是由于数据结构的高效性掩盖了一部分的coding设计不良之处…
之前我也有在遍历每一层之后将这一层的结点从dict中全部去掉，不知道是否还漏了什么优化技巧…。

这题也是大数据过不了！我也想试试adjacent linkedlist！

import java.util.*;

public class WordLadderII {

        public static ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {

        if (start == null || end == null || dict == null) return null;

        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();

        ArrayList<String> toRemove = new ArrayList<String>();

        HashMap<String, HashSet<String>> traces = new HashMap<String, HashSet<String>>();

        Queue<String> queue = new LinkedList<String>();

        Queue<Integer> layer = new LinkedList<Integer>();

        double minLength = Double.POSITIVE_INFINITY;

        int pre = 1;

        queue.add(start);

        layer.add(1);

        while (queue.size() > 0) {

                String cur = queue.remove();

                int distance = layer.remove();

               

                if (distance < minLength){

                        for (int i = 0; i < start.length(); i++) {

                                for (char symbol = 'a'; symbol <= 'z'; symbol++) {

                                        char[] charArray = cur.toCharArray();

                                        if (charArray[i] == symbol) continue;

                               

                                        charArray[i] = symbol;

                               

                                        String conversion = String.valueOf(charArray);

                               

                                        if (conversion.equals(end)) {

                                                if (distance + 1 <= minLength) {

                                                        if (traces.containsKey(conversion)) traces.get(conversion).add(cur);

                                                    else {

                                                            HashSet<String> temp = new HashSet<String>();

                                                           

                                                            temp.add(cur);

                                                            traces.put(conversion, temp);

                                                    }

                                                }

                                        }

                                        else if (dict.contains(conversion)) {

                                                if (pre == distance) toRemove.add(conversion);

                                                else {

                                                        pre = distance;

                                                       

                                                        for (String str : toRemove) dict.remove(str);

                                                       

                                                        toRemove.clear();

                                                        toRemove.add(conversion);

                                                }

                                               

                                                if (traces.containsKey(conversion)) traces.get(conversion).add(cur);

                                                else {

                                                        HashSet<String> temp = new HashSet<String>();

                                                       

                                                        temp.add(cur);

                                                        traces.put(conversion, temp);

                                                }

                                               

                                                queue.add(conversion);

                                                layer.add(distance+ 1);

                                        }

                                }

                        }

                }

        }

        ArrayList<String> path = new ArrayList<String>();

        path.add(end);

        if (traces.size() != 0)

                buildPath(end, start, path, traces, result);

        return result;

    }

       

        public static void buildPath(String start,

                                                                String target,

                                                                ArrayList<String> path,

                                                                HashMap<String, HashSet<String>> traces,

                                                                ArrayList<ArrayList<String>> result) {

                if (start.equals(target)) {

                        result.add(new ArrayList<String>(path));

                }

                else {

                        for (String str : traces.get(start)) {

                                        path.add(0, str);

                                        buildPath(str, target, path, traces, result);

                                        path.remove(0);

                        }

                }

        }

        public static void main(String[] args) {

                ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();

                HashSet<String> dict = new HashSet<String>(Arrays.asList("hot", "dog"));

                String start = "hot", end = "dog";

               

                result = findLadders(start, end, dict);

               

                for (ArrayList<String> path : result) {

                        System.out.print(path);

                }

        }

}

这题java好难过啊...要注意的细节太多了　-　＝　

得大牛指点，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. }

复制代码

谢谢楼上的同学
真心谢谢你
这个题目，研究好久（不好意思，水平太差了。。。）
网上好多代码都没有注释的
这个写的清清楚楚明明白白，很感激
我的权限貌似只有这么多分可以给你，不好意思了

C++版本，600ms过大数据。 hope it helps

不再逐个替换字母，而是从start出发，遍历start的邻接顶点，将邻接顶点放入队列中。并重复操作直到队列为空

还有一个发生变化的地方是去重操作。由于不再遍历字典，现在我们发现非同层出现重复的单词就跳过它而不是从字典里删去。


class Solution {
    // function to generate path using backtracking method
    void gen(int v1, int v2, vector<string> &vdict, vector<vector<int> >& prev,
             vector<int>& path, vector<vector<string> >&ans){
              
        path.push_back(v2); // push the nodes into path for back tracking
         
        if(v2 == v1 and path.size() > 1){
            ans.push_back(vector<string>());
            // translate the path of index to string in reverse order
            for(auto rit = path.rbegin(); rit != path.rend(); rit++)
                ans.back().push_back(vdict[*rit]);
        }else{
            // gengrate all possible path in recursive way
            for(int i = 0; i < prev[v2].size(); i++)
                gen(v1, prev[v2][i], vdict, prev, path, ans);
        }
         
        path.pop_back(); // pop the nodes from path for back tracking
    }
public:
    vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
        dict.insert(start);
        dict.insert(end);
         
        vector<string> vdict(dict.begin(), dict.end()); // vector dictionary: id -> word mapping in dict
        unordered_map<string, int> ids;  // index dictionary: word -> id mapping in vdict
        vector<vector<int> > prev(dict.size()); // store the previous words in BFS
        vector<int> distance(dict.size(), -1); // store the distance from start
         
        // build string - index mapping, transfer problem to graph search
        // use interger instead of string to eliminate cost of string matching
        for(int i = 0; i < vdict.size(); i++)
            ids[vdict[i]] = i;
         
        // find the index of start and end words
        int vstr=0, vend=0;
        while(vdict[vstr] != start) vstr++;
        while(vdict[vend] != end) vend++;
         
        // use queue for BFS to search path from start to end
        queue<int> que;
        que.push(vstr);
        distance[vstr]=0;
         
        while(not que.empty()){
            int v1 = que.front(); que.pop();
            if(v1 == vend) break;
            int d = distance[v1] + 1;
            
            // get adjancent list of the words, branching factor of BFS is 26 characters * string size
            vector<int> adj;
            // erase the appeared words from dictionary can save search time
            ids.erase(vdict[v1]);
            
            // find all the words that can be transfered in 1 step
            for(int j = 0; j < vdict[v1].size(); j++){
                char w = vdict[v1][j];
                for(char c = 'a'; c <= 'z'; c++){
                    vdict[v1][j] = c;
                    if(ids.count(vdict[v1]))
                        adj.push_back(ids[vdict[v1]]);
                    vdict[v1][j] = w;
                }
            }
            
            // use BFS to calculate path to end, add new words (distance=-1) into queue
            // if multiple words can reach the same words, save all the words
            for(int i = 0; i < adj.size(); i++){
                int v = adj[i];
                if(distance[v] == -1){
                    prev[v].push_back(v1);
                    distance[v] = d;
                    que.push(v);
                }else if(distance[v] == d){
                    prev[v].push_back(v1);
                }
            }
        }

        // generate the full sting path using the index
        vector<vector<string> > ans;
        vector<int> path;
        gen(vstr, vend, vdict, prev, path, ans);
        return ans;
    }

};

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

Clear illustration.

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