TLE: both dfs and bfs get TLE, please help optimize it


  • 1
    E
      /*
    
    Word Ladder II
    
    Given two words (start and end), and a dictionary,
    find all shortest transformation sequence(s)
    from start to end, 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
    
    */
    
    #include <iostream>
    #include <queue>
    #include <string>
    #include <unordered_set>
    #include <unordered_map>
    #include <map>
    #include <set>
    #include <climits>
    
    using namespace std;
    
    // DFS
    // cannot pass OJ, TLE
    class Solution {
    	public:
    		void dfs(vector<vector<string>> &ret, vector<string> &transform, size_t maxLen, string start,
    				const string &end, unordered_set<string> &dict, unordered_set<string> &used) {
    			size_t curLen = transform.size();
    			if (curLen > maxLen) return;
    
    			if (start == end) {
    				if (ret.empty() || ret[0].size() == curLen) {
    					ret.push_back(transform);
    				} else if (ret[0].size() > curLen) {
    					ret.clear();
    					ret.push_back(transform);
    				}
    
    				maxLen = curLen; // decrease search depth
    				return;
    			}
    
    			string t(start);
    			for (size_t i = 0; i < end.size(); i++) {
    				for (char c = 'a'; c <= 'z'; c++) {
    					if (t[i] == c) continue; // itself
    
    					t[i] = c;
    					// t is not used and in the dict
    					if (used.find(t) == used.end() &&
    							dict.find(t) != dict.end()) {
    						used.insert(t);
    						transform.push_back(t);
    						dfs(ret, transform, maxLen, t, end, dict, used);
    						used.erase(t);
    						transform.pop_back();
    					}
    				}
    
    				t[i] = start[i]; // reset t to cur
    			}
    		}
    
    
    		vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
    			vector<vector<string>> ret;
    
    			size_t len = start.size();
    			if (len != end.size() || len == 0 || start == end) return ret; // invalid
    
    			unordered_set<string> used;
    			vector<string> transform;
    			size_t maxLen = INT_MAX;
    
    			// prepare, be carefull about adding end to dict...
    			transform.push_back(start);
    			dict.insert(end);
    
    			dfs(ret, transform, maxLen, start, end, dict, used);
    
    			return ret;
    		}
    };
    
    // BFS
    // cannot pass OJ, TLE
    // unordered_map<string, unordered_set<string>> &father can be unordered_multimap<string, string>
    // gcc 4.8 ran into build error when use equal_range...
    class Solution2 {
    	public:
    		void getPath(string &start, string &end, unordered_set<string> &dict,
    				unordered_map<string, unordered_set<string>> &father, vector<vector<string>> &ret, vector<string> &path) {
    			path.push_back(start);
    			if (start == end) {
    				ret.push_back(vector<string>(path.rbegin(), path.rend()));
    			} else {
    				for (auto e : father[start]) {
    					getPath(e, end, dict, father, ret, path);
    				}
    			}
    			path.pop_back();
    		}
    
    		void bfs(string &start, string &end, unordered_set<string> &dict,
    				vector<vector<string>> &ret) {
    			size_t len = start.size();
    			if (len != end.size() || len == 0 || start == end) return; // invalid
    
    			unordered_set<string> used;
    			unordered_set<string> levelUsed;
    			unordered_map<string, unordered_set<string>> father; // use it to get path
    
    			queue<string> q;
    			q.push(start);
    			int levelSize = 0;
    			bool found = false;
    
    			while (!q.empty()) {
    				if (levelSize == 0) { // finish one level
    					if (found) break;
    					levelSize = q.size();
    					for (auto e : levelUsed) used.insert(e);
    					levelUsed.clear();
    				}
    
    				string cur = q.front();
    				string t(cur);
    				q.pop();
    				levelSize--;
    
    				for (size_t i = 0; i < len; i++) {
    					for (char c = 'a'; c <= 'z'; c++) {
    						if (t[i] == c) continue; // itself
    
    						t[i] = c;
    						if (t == end) { // find it
    							found = true;
    							father[t].insert(cur);
    							break;
    						}
    
    						// t is not used and is in the dict
    						if (used.count(t) == 0 && dict.count(t) != 0) {
    							q.push(t);
    							levelUsed.insert(t);
    							father[t].insert(cur);
    						}
    					}
    					t[i] = cur[i]; // reset t to cur
    				}
    			}
    
    			if (found) {
    				vector<string> path;
    				getPath(end, start, dict, father, ret, path);
    			}
    		}
    
    		vector<vector<string>> findLadders(string &start, string &end, unordered_set<string> &dict) {
    			vector<vector<string>> ret;
    			bfs(start, end, dict, ret);
    			return ret;
    		}
    };
    
    void print_ret(vector<vector<string>> &ret) {
    	for (auto &row : ret) {
    		for (auto e : row) {
    			cout << e << ' ';
    		}
    		cout << endl;
    	}
    }
    
    int main(int argc, char *argv[]) {
    	Solution sol;
    	Solution2 sol2;
    
    	string start("hit");
    	string end("cog");
    	unordered_set<string> dict = {"hot","dot","dog","lot","log"};
    
    	// bug
    	string start1("red");
    	string end1("tax");
    	unordered_set<string> dict1 = {"ted","tex","red","tax","tad","den","rex","pee"};
    
    	vector<vector<string>> ret;
    
    	sol.findLadders(start, end, dict);
    	print_ret(ret);
    	ret = sol2.findLadders(start, end, dict);
    	print_ret(ret);
    
    	ret = sol.findLadders(start1, end1, dict1);
    	print_ret(ret);
    	ret = sol2.findLadders(start1, end1, dict1);
    	print_ret(ret);
    
    	return 0;
    }

  • 4
    Y

    I've modified your bfs version and get it accepted.

    The problem is that your algorithm pushes a word into the queue every time it is not used and in the dict. Instead, you should push newly found words into the queue when a level is finished.

    Code:

    // BFS
    class Solution {
    public:
        void getPath(string &start, string &end, unordered_set<string> &dict,
                unordered_map<string, unordered_set<string>> &father, vector<vector<string>> &ret, vector<string> &path) {
            path.push_back(start);
            if (start == end) {
                ret.push_back(vector<string>(path.rbegin(), path.rend()));
            } else {
                for (auto e : father[start]) {
                    getPath(e, end, dict, father, ret, path);
                }
            }
            path.pop_back();
        }
    
        void bfs(string &start, string &end, unordered_set<string> &dict,
                vector<vector<string>> &ret) {
            size_t len = start.size();
            if (len != end.size() || len == 0 || start == end) return; // invalid
    
            unordered_set<string> used;
            unordered_set<string> levelUsed;
            unordered_map<string, unordered_set<string>> father; // use it to get path
    
            queue<string> q;
            q.push(start);
            int levelSize = 1;
            bool found = false;
    
            while (!q.empty()) {
                string cur = q.front();
                string t(cur);
                q.pop();
                levelSize--;
    
                for (size_t i = 0; i < len; i++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (t[i] == c) continue; // itself
    
                        t[i] = c;
                        if (t == end) { // find it
                            found = true;
                            father[t].insert(cur);
                            break;
                        }
    
                        // t is not used and is in the dict
                        if (used.count(t) == 0 && dict.count(t) != 0) {
                            //q.push(t);
                            levelUsed.insert(t);
                            father[t].insert(cur);
                        }
                    }
                    t[i] = cur[i]; // reset t to cur
                }
                
                if (levelSize == 0) { // finish one level
                    if (found) break;
                    for (auto e : levelUsed) {used.insert(e); q.push(e);}
                    levelSize = q.size();
                    levelUsed.clear();
                }
            }
    
            if (found) {
                vector<string> path;
                getPath(end, start, dict, father, ret, path);
            }
            
        }
    
        vector<vector<string>> findLadders(string &start, string &end, unordered_set<string> &dict) {
            vector<vector<string>> ret;
            bfs(start, end, dict, ret);
            return ret;
        }
    };

  • 0
    Y
    This post is deleted!

  • 0
    E

    thank you. it works well.
    Actually, it pushes all used words to queue and dict (not non-used)...
    but it includes duplicate words...my algorithm works because I used
    unordered_map<string, unordered_set<string>> in the father definition.

    I switched to unordered_multimap<string, string> after upgrade gcc to 4.8.2
    and then found the bug.
    Each level must not have duplicate words.


  • 0
    S

    i guess you mean his "BFS" solution.
    I tried various ways with DFS,including a prior BFS providing the correct depth of search
    they just TLE, i guess one cannot affort repeatedly visit the same nodes in different iteration while DFS is doing exactly that.


  • 0
    L

    Are you sure DFS works for this problem? I think DFS can never be relied on for shortest path problems, because its uncertainty when selecting next unvisited neighbor


  • 0
    L

    Very neat solution. I was also stuck at TLE. Just a slight modification, I think levelSize is unnecessary.
    if(levelSize==0) --> if(q.empty())


  • 0
    N

    used.insert(e) move to the start of while(), like this:
    string cur = q.front();
    used.insert(cur);
    Memory Limit Exceeded occur ,Why?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.