Wrong Answer...I really don't why...need help...Thank you!


  • 1
    Z

    class Solution {
    public:

    void findPath(string start, string end, unordered_map<string, string> &path, vector<string> &rt) {
    	rt.push_back(end);
    	string t = end;
    	while(path[t] != start) {
    	    rt.push_back(path[t]);
    	    t = path[t];
    	}
    	rt.push_back(start);
    }
    
    
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        vector<vector<string> > res;
        if(start == end) {
            res.push_back(vector<string> (2, start));
            return res;
        }
        unordered_set<string> setInCurr;//set in current level
        unordered_set<string> totalSet;//total set
        totalSet.insert(start);
        unordered_map<string, string> path;
        queue<string> qCurr;
        queue<string> qNext;
        queue<string> qClear;
        qCurr.push(start);
        vector<string> rt;
        while(!qCurr.empty()) {
            string temp = qCurr.front();
            qCurr.pop();
            for(int i = 0; i < start.size(); ++i) {
                for(int j = 0; j < 26; ++j) {
                    string temp1 = temp;
                    temp1[i] = 'a' + j;
                    if(temp1 == end) {
                        path[end] = temp;
                        findPath(start, end, path, rt);
                        path.erase(end);
                        reverse(rt.begin(), rt.end());
                        res.push_back(rt);
                        while(!qCurr.empty()) {
                            string temp = qCurr.front();
                            qCurr.pop();
                            for(int i = 0; i < start.size(); ++i) {
                                for(int j = 0; j < 26; ++j) {
                                	string temp1 = temp;
                                	temp1[i] = 'a' + j;
                                	if(temp1 == end) {
                                	    rt.clear();
                                	    path[end] = temp;
                                		findPath(start, end, path, rt);
                                		path.erase(end);
                                		reverse(rt.begin(), rt.end());
                                		res.push_back(rt);
                                	}
                                }
                            }
                        }
                        return res;
                    }
                    if(dict.find(temp1) != dict.end() && totalSet.find(temp1) == totalSet.end()) {
                        qNext.push(temp1);
                        path[temp1] = temp;
                        setInCurr.insert(temp1);
                    }
                }
            }
            if(qCurr.empty()){
                totalSet.insert(setInCurr.begin(), setInCurr.end());
                setInCurr.clear();
                qCurr = qNext;
                qNext = qClear;;
            }
        }
    }
    

    };

    Time Limit Exceeded
    Last executed input: "nanny", "aloud", ["ricky","grind","cubic","panic"......]

    Why? Thank you!
    My algorithm:
    I use two queues to traverse the tree by level(visit the word in qCurr and push their children into qNext. When the qCurr is empty, let qCurr = qNext and clear qNext) and store the path in a map, in which the key is the word in current level, and the value is the word in previous level. When a word hit the end, I will find the path using the map and go on with the word in qCurr to see if the next word in qCurr can hit the end(In this way, I can guratee the path is the shortest).


  • 0
    S

    Please tell your brief algorithm of your solution in some words. It might help to go thru your code.


  • 0
    Z
    This post is deleted!

  • 0
    Z
    This post is deleted!

  • 0
    Z
    This post is deleted!

  • 0
    Z
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    Y
    if(dict.find(temp1) != dict.end() && path.find(temp1) == path.end() 
        && temp != start) {//start is not the key in path
        qNext.push(temp1);
        path[temp1] = temp;
    }
    

    Here qNext is empty after the first iteration of the loop, since temp always equals start.

    However, Your algorithm is not correct for the question, because it only find some paths instead of all paths.


  • 0
    Z

    I have modify my answer:
    I use two unordered_set to record the words that I have visited. setInCurr records the words that in current level and totalSet records those before current level. After traverse one level, I will add setInCurr into totalSet.
    But as you see, there's a new problem... Can you help me? I'm a new coder. Thank you for your help!


  • 0
    Y

    I think you may search the web for a solution and figure out how it works, then write your own code. Or you can just skip this problem and try some easier ones. (You know, the difficulty of this question is above the average.)


  • 0
    S

    Please format the code in your question correctly.


Log in to reply
 

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