Time Limit Exceeded for "nape", "mild"


  • 7
    C

    I used BFS approach and kept a map for getting paths. I used dp approach for faster retrievel but i am still getting TLE for "nape" "mild" input (achieved to get correct results on my pc). Can anyone point ways to decrease time consumption?

    public ArrayList<ArrayList<String>> findLadders(String start,
    			String end, HashSet<String> dict) {
    
    		ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
    		Queue<String> que = new LinkedList<String>();
    		que.add(start);
    		String dummy = "dummuuuOO";
    		HashSet<String> used = new HashSet<String>();
    		if (!dict.contains(end))
    			return ret;
    		que.add(dummy);
    		dict.remove(start);
    		HashMap<String, Set<String>> path = new HashMap<String, Set<String>>();
    		HashSet<String> usedTemp = new HashSet<String>();
    		HashMap<String, ArrayList<String>> dictMemory = new HashMap<String, ArrayList<String>>();
    		int count = 0;
    		while (que.size() > 1) {
    			String current = que.poll();
    			if (current.equals(end)) {
    				HashMap<String, ArrayList<ArrayList<String>>> mem = new HashMap<String, ArrayList<ArrayList<String>>>();
    				ret.addAll(generateList(start, end, path, mem, count));
    				break;
    			}
    			if (current.equals(dummy)) {
    				count++;
    				que.add(dummy);
    				used.addAll(usedTemp);
    				usedTemp.clear();
    				continue;
    			}
    			ArrayList<String> list = getNextFromDict(current, dict, dictMemory, end);
    			for (String next : list) {
    				if (!used.contains(next)) {
    					Set<String> nl = path.get(next) == null ? new HashSet<String>()
    							: path.get(next);
    					nl.add(current);
    					path.put(next, nl);
    					usedTemp.add(next);
    					que.add(next);
    				}
    			}
    		}
    		return ret;
    	}
    
    	private  ArrayList<String> getNextFromDict(String current,
    			HashSet<String> dict, HashMap<String, ArrayList<String>> dictMemory, String last) {
    		if (dictMemory.get(current) != null)
    			return dictMemory.get(current);
    		ArrayList<String> ret = new ArrayList<String>();
    		for (int n = 0; n < current.length(); n++) {
    			String check = current.substring(0, n) + String.valueOf(last.charAt(n))
    					+ current.substring(n + 1);
    			if (dict.contains(check))
    				ret.add(check);
    			for (char c = 'a'; c < 'z'; c++) {
    				if (current.charAt(n) != c && last.charAt(n) != c) {
    					String key = current.substring(0, n) + String.valueOf(c)
    							+ current.substring(n + 1);
    					if (dict.contains(key))
    						ret.add(key);
    				}
    			}
    		}
    		dictMemory.put(current, ret);
    		return ret;
    	}
    
    	private  ArrayList<ArrayList<String>> generateList(String start,
    			String end, HashMap<String, Set<String>> path,
    			HashMap<String, ArrayList<ArrayList<String>>> memory, int count) {
    		ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
    		if (count < 0)
    			return null;
    		if (memory.get(end) != null) {
    			if (memory.get(end) != null && memory.get(end).size() > 0
    					&& memory.get(end).get(0).size() == count+1){
    				ArrayList<ArrayList<String>> cache1 = new ArrayList<ArrayList<String>>();
    				ArrayList<String> cache2 = new ArrayList<String>();
    				cache2.addAll(memory.get(end).get(0));
    				cache1.add(cache2);
    				return cache1;
    			}
    			else
    				return null;
    		}
    		String key = end;
    		if (key.equals(start)) {
    			ArrayList<String> l = new ArrayList<String>();
    			l.add(key);
    			ret.add(l);
    			ArrayList<ArrayList<String>> retClone = new ArrayList<ArrayList<String>>();
    			for (ArrayList<String> list : ret) {
    				ArrayList<String> lClone = new ArrayList<String>();
    				lClone.addAll(list);
    				retClone.add(lClone);
    			}
    			memory.put(end, retClone);
    			return ret;
    		}
    
    		Set<String> prev = path.get(key);
    		for (String p : prev) {
    			ArrayList<ArrayList<String>> generateList = generateList(start, p,
    					path, memory, count-1);
    			if (generateList != null) {
    				for (ArrayList<String> pth : generateList) {
    					pth.add(key);
    					ret.add(pth);
    				}
    			}
    		}
    		ArrayList<ArrayList<String>> retClone = new ArrayList<ArrayList<String>>();
    		for (ArrayList<String> list : ret) {
    			ArrayList<String> lClone = new ArrayList<String>();
    			lClone.addAll(list);
    			retClone.add(lClone);
    		}
    		memory.put(end, retClone);
    		return ret;
    	}

  • 1
    L

    I got the same problem, my solution cost less than 1 second for this test case when running on my laptop, still don't know why.


  • 0
    K

    One second, in 2010s, is a long time.


  • 1
    X
    if (start == "nape")
        return vector<vector<string>>();
    

    even this code can not pass this case, still TLE.


  • 0
    N

    start == "nape" is false, you may need to use "start.equals("nape")"


  • 0
    X

    I use c++ not java. I have passed with some optimization.


  • 0
    C

    My program costs only 16ms on my laptop, but still got TLE.


  • 0
    W

    I also have the same problem.
    My code takes 0.02 seconds for this input on my computer, but still TLE here

    I also tried in Python

    if start=='nape': return [[]]
    

    'start=='nape' is fine on python, but still TLE


  • 0
    C

    I got the same problem for "nape" and "mild", and I tried to skip calculation for this case, still got TLE.
    something wrong with this problem?


  • 1
    C

    python around 0.004 ~ 0.006 s, still TLE. Give up


  • 1
    X

    I finally passed using c++. Here's what I've found:

    Either the machine leetcode used to run your program is too slow or the
    problem has a much more stricter time limitation.

    Even if you passed the testcase ("nape", "mild") on your laptop for less than 0.01s,
    you may still TLE on the testcase ("charge", comedo"), which costs just 0.16s on my laptop.
    I found that building the graph costs most (no matter O(n^2) or O(n *
    length_of_string * 26) plus a whatever hashtable).

    So I turned to build a Trie, and find all strings that differs from a given string at
    exactly one position. This gives me a running time of 0.01s on the ("charge", comedo") testcase
    and finally got accepted.

    Here is what the Trie looks like. Hope this will be of help.

    class Trie {
    	public:
    		struct Node {
    			int id;
    			Node *next[26];
    			Node() {
    				memset(next, 0, sizeof(next));
    			}
    		};
    
    		Trie() {
    			root = new Node();
    		}
    		~Trie() {
    			release(root);
    		}
    
    		void release(Node *node)  {
    			if (node == nullptr)
    				return;
    			for (auto &n: node->next)
    				release(n);
    		}
    
    		Node *root;
    		void add(const string &s, int id) {
    			Node *cur = root;
    			for (auto &c: s)
    				cur = add(cur, c);
    			cur->id = id;
    		}
    
    		Node *add(Node *cur, char c) {
    			int idx = c - 'a';
    			if (cur->next[idx])
    				return cur->next[idx];
    			return cur->next[idx] = new Node();
    		}
    
    		template<class func_t>
    			void visit_diff_one(const string &s, func_t &&callback) {
    				Node *cur = root;
    				for (size_t i = 0; i < s.length(); i ++) {
    					for (int j = 0; j < 26; j ++) {
    						Node *front = cur->next[j];
    						if (!front)
    							continue;
    						for (int k = i + 1; k < (int)s.length() && front; k ++)
    							front = front->next[s[k] - 'a'];
    						if (front) {
    							callback(front->id);
    						}
    					}
    					cur = cur->next[s[i] - 'a'];
    				}
    			}
    };
    

  • 0
    C

    With some optimization, it accepted. The total time for the accepted solution is 1980 ms.


  • 5
    A

    here is my code, it got passed in less than 700ms, here is my solution:
    first use bfs to create the graph, and by using data structure like unordered_multimap and unordered_set, I can enhance the speed, one important thing is to change letter to get the interval word, not by comparing each word in the dict.
    after getting the graph, use dfs to find all the paths from start to end.I hope this would help you.

    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);
            
            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;
    
                    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;
                curr_layer = last_layer;
            }
            
            vector<string> path;
    
            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;
                    visited.insert(prev);
                    
                    get_path(prev, start, path);
                    
                    visited.erase(prev);
                    if (!path.empty())
                        path.erase(path.begin());
                }
                ++it;
            }
        }
    };
    

  • 0
    L

    Yes you are right. The key is not to compare each word in the dict. This can be achieved by changing each char of the word or using a Trie, the one as @xinyu5 mentioned.


  • 0
    J

    Got the same issue. In my machine, it takes 14 ms.


  • 0
    M

    The str in python is immutable. I try to memorize the neighbors (the words that only have a char difference) and it helps. Another way is giving up python. I used c++ and got 6xx ms.


  • 0
    D

    I use Java to solve the problem with BFS, and reach 0.007s for this test case on my computer , but also got a TLE. It makes me confused, could I still optimize it?


  • 0
    L

    "change letter to get the interval word, not by comparing each word in the dict". This is really useful!


  • 0
    I
    This post is deleted!

  • 0
    G

    me too, only 0.007s on my computer, can't understand why


Log in to reply
 

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