1804ms with C++, any better solution?


  • 0
    T
    class Solution {
    public:
        vector<vector<string>> helper(unordered_map<string,vector<string>> &pre,string s,unordered_map<string,int>&visit,string start){
            vector<vector<string> > ret,ret1;vector<string> t_ret;
            if(s==start) {t_ret.push_back(s);ret.push_back(t_ret);return ret;}
            for ( auto it = pre[s].begin(); it != pre[s].end(); ++it ){
                ret1=helper(pre,*it,visit,start);
                for(int i=0;i<ret1.size();i++){
                    ret1[i].push_back(s);
                    ret.push_back(ret1[i]);
                } ret1.clear();
            }
            return ret;
        }
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
            unordered_map<string,vector<string> > graph;unordered_map<string,int> visit;unordered_map<string,vector<string>> pre;
            vector<vector<string> > ret; vector<string> t_ret;
    		if(start==end){t_ret.push_back(start);t_ret.push_back(end);ret.push_back(t_ret);return ret;}
    		dict.insert(start);dict.insert(end);
            for ( auto it = dict.begin(); it != dict.end(); ++it ){
                string t=*it; visit[t]=0;
                for(int i=0;i<t.size();i++)
                    for(int j='a';j<='z';j++){
                        if(char(j)==t[i]) continue;
                        string tt=t;
    					tt[i]=char(j);
                        if(dict.count(tt)>0) graph[t].push_back(tt);
    				}
            }
            queue <string> myq;
            myq.push(start);
            while(!myq.empty()){
                for(int i=0;i<graph[myq.front()].size();i++){
                    if( visit[graph[myq.front()][i]]==0){
                        visit[graph[myq.front()][i]]=visit[myq.front()]+1;
                        myq.push(graph[myq.front()][i]);
                        pre[graph[myq.front()][i]].push_back(myq.front());
    				}
                    else if(visit[graph[myq.front()][i]]>0&&visit[graph[myq.front()][i]]>=visit[myq.front()]+1){
                        if(visit[graph[myq.front()][i]]>visit[myq.front()]+1){
                            visit[graph[myq.front()][i]]=visit[myq.front()]+1;
                             pre[graph[myq.front()][i]].push_back(myq.front());
                        }else  pre[graph[myq.front()][i]].push_back(myq.front());;
                    }
                }
                visit[start]=1;
    			myq.pop();
            }
            if(visit[end]==0) return ret; 
            ret=helper(pre,end,visit,start);
            return ret;
        }
    };`enter code here`

Log in to reply
 

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