Clean c++ solution, maybe not fast enough


  • 1
    N
    class Solution {
    private:
        unordered_map<string, vector<string>> dfsGraph;
        vector<vector<string>> result;
    public:
        void dfs(vector<string> chosen, string word, string beginWord){
            chosen.push_back(word);
            if(word == beginWord){
                reverse(chosen.begin(), chosen.end());
                result.push_back(chosen);
                return;
            }
            for(auto it=dfsGraph[word].begin();it!=dfsGraph[word].end();it++){
                dfs(chosen, *it, beginWord);
            }
        }
        vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
            if(beginWord.empty() || beginWord == endWord) return result;
            queue<string> q;
            unordered_set<string> visited;
            wordList.insert(endWord);
            wordList.erase(beginWord);
            q.push(beginWord);
            //bfs
            while(!q.empty()){
                int n = q.size();
                for(int i=0;i<n;i++){
                    string word = q.front();
                    q.pop();
                    if(word == endWord){
                        dfs(vector<string>(), word, beginWord);
                        return result;
                    }
                    string prev = word;
                    for(int i=0;i<word.length();i++){
                        char c = word[i];
                        for(int j=0;j<26;j++){
                            word[i] = 'a' + j;
                            if(wordList.find(word) != wordList.end()){
                                //ignore duplicate same level word
                                if(visited.insert(word).second) q.push(word);
                                dfsGraph[word].push_back(prev);
                            }
                        }
                        word[i] = c;
                    }
                }
                for(auto it=visited.begin();it!=visited.end();it++){
                    wordList.erase(*it);
                }
                visited.clear();
            }
            //make compiler happy
            return result;
        }
    };
    

Log in to reply
 

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