[Word-ladder] [Time-Limit-Exceeded]: already used a BFS approach, but still got TLE error


  • 0
    W

    I have faced the same problem: Time Limit Exceeded for inputs: "sand", "acne", ["slit".
    I feel my approach is elegant (one thing can be improved is using BFS from both front and end). There must be a certain operation which takes relative long time. Can some one help?

    class Solution {
    public:
        int ladderLength(string start, string end, unordered_set<string> &dict) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
    		if((!start.length()) || (start.length()!=end.length())) return 0;
    		int results=1;
    		string cur;
    		queue <string> startPending;
    		unordered_set <string> alreadyVisit;
    		startPending.push("\0");
    		startPending.push(start);
    		while(!startPending.empty())
    		{
    			cur = startPending.front(); startPending.pop();
    			if (cur == "\0")
    			{
    				if (!startPending.empty()) { results++; startPending.push("\0"); } //"\0" is used to note the level, whenever see a "\0" string, add results count
    				else return 0; //This means BFS has completed, not able to find a solution for word ladder.
    			}
    			else
    			{
    				alreadyVisit.insert(cur);
    				//generate different types of string, check if the string matches the end, else check if the string is in the alreadyVisit set, if not discard it.
    				for (int i = 0; i < cur.size(); i++)
    				{
    					for (char temp = 'a'; temp <= 'z'; temp++)
    					{
    						string tempS = cur;
    						tempS[i] = temp;
    						if (tempS == end) return results;
    						if (alreadyVisit.find(tempS) == alreadyVisit.end())
    						if (dict.find(tempS) != dict.end())	startPending.push(tempS);
    					}
    				}
    			}
    		}
    		return 0;
        }
    };

  • 3
    S

    I think I get your problem.

    You did it alreadyVisit.insert(cur); for the current word, which means it is expending this word now. But you need to insert it when pushing the word into the bfs queue startPending immediately. Or you will have large amount of duplicated words saved in the queue, but do not insert in the alreadyVisit yet. It will lead to bunch of expending same words, which must waste the run time.


  • 1
    P

    Besides the problem that Shangrila points out here, there is one factor that result in the Time Limit Exceeded Verdict.

    You should not create string tempS every time you search for a new char temp, you should reuse it to avoid too many copy of tempS.


  • 0
    W

    Thanks. You are Super! BTW, does unordered_set.find() have the same time complex of unordered_set.count()?


  • 0
    W

    Thanks, I am not good at memory management. I was afraid queue.push() need a unique an instance. So queue.push() will create a new memory for the new element? How about vector.push_back(), same as queue?


  • 0
    S

    yes, I think so. Their complexity of average case are both constant.


  • 0
    X

    I think intepreter only use one instance of the same String.


  • 0
    I

    Ah... I guess I over killed this problem by using a trie tree.


Log in to reply
 

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