C++ BFS solution


  • 1
    B
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> ans;
        if(wordList.empty())
            return ans;
        vector<vector<string>> q(1, vector<string>());
        map<string, bool> visited;
        for(int i=0; i<wordList.size(); ++i)
            visited[wordList[i]]=false;
        if(visited.find(endWord)==visited.end())
            return ans;
        q[0].push_back(beginWord);
        visited[beginWord]=true;
        bool found=false;
        for(int i=0; i<q.size(); ++i){
            for(int j=0; j<q[i].size(); ++j){
                string s=q[i][j];
                for(int k=0; k<s.length(); ++k){
                    char _c=s[k];
                    for(int l=0; l<26; ++l){
                        s[k]='a'+l;
                        if(visited.find(s)!=visited.end()&&!visited[s]){
                            if(s==endWord)
                                found=true;
                            if(q.size()==i+1)
                                q.push_back(vector<string>());
                            q[i+1].push_back(s);
                            visited[s]=true;
                        }
                    }
                    s[k]=_c;
                }
                if(found)
                    break;
            }
            if(found)
                break;
        }
        if(!found)
            return ans;
        q.pop_back();
        vector<string> tmp(1, endWord);
        solve(q, q.size()-1, ans, tmp);
        return ans;
    }
    void solve(vector<vector<string>> &q, int cur, vector<vector<string>> &ans, vector<string> &v){
        if(cur==0){
            v.push_back(q[cur][0]);
            ans.push_back(v);
            v.pop_back();
            reverse(ans.back().begin(), ans.back().end());
            return;
        }
        for(int i=0; i<q[cur].size(); ++i){
            if(check(q[cur][i], v.back())){
                v.push_back(q[cur][i]);
                solve(q, cur-1, ans, v);
                v.pop_back();
            }
        }
    }
    bool check(const string &a, const string &b){
        int cnt=0;
        for(int i=0; i<a.length(); ++i){
            if(a[i]!=b[i])
                ++cnt;
        }
        return cnt==1;
    }

Log in to reply
 

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