[one-of-the-most-hard-problem]clean C++ implementation


  • 2

    My implementation can not pass the case:

        start:  "a"
    
        end : "c"
    
        dict=["a", "b, "c"]
    

    My code will return [ ] but the right answer is [["a", "c"]]

    Here is my implementation:

    class Solution {  
    public:
        vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
            int min_depth=0;
            vector<vector<string>> result;
            vector<string> ladder;
            unordered_set<string> set_ladder;
            ladder.push_back(beginWord);
            help(beginWord, endWord, wordList, ladder, result, set_ladder, 0, min_depth);
            return result;
        }
        
        void help(string cur, string endWord, unordered_set<string> &wordList, vector<string> ladder, vector<vector<string>>& result, unordered_set<string>& set_ladder, int depth, int& min_depth){
            if(cur==endWord){
                cout<<"find"<<endl;
                if(min_depth==0)  {
                    min_depth=depth;
                    result.push_back(ladder);
                }
                else if(depth == min_depth){
                    result.push_back(ladder);
                }
                return;
            }
            
            for(int i=0; i<cur.size(); i++){
                for(int j=0; j<26 && j!=cur[i]-'a'; j++){
                    string temp = cur;
                    temp[i]='a'+j;
                    if(wordList.find(temp)!=wordList.end() && set_ladder.find(temp)==set_ladder.end()){
                        ladder.push_back(temp);
                        set_ladder.insert(temp);
                        help(temp, endWord, wordList, ladder, result, set_ladder, depth+1, min_depth);
                    }
                }
            }
            return;
        }
    };

  • 1
    class Solution {
    public:
        vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList){ 
            unordered_set<string> current, next;
            unordered_set<string> visited;
            /*** the key-part-structure : record-the-father-relation-ship-to-reconstruct-all-possible-path ***/
            unordered_map<string, vector<string>> father;
            vector<vector<string>> result;
            
            current.insert(beginWord);
            while(!current.empty()){
                for(const auto& state : current)
                    visited.insert(state);
                for(const auto& state : current){
                    if(state_is_target(state, endWord)){
                        vector<string> path;
                        gen_path(father, path, beginWord, state, result);
                    }
                    const auto new_states = state_extend(state, endWord, wordList, visited);
                    for(const auto& new_state : new_states){
                        next.insert(new_state);
                        father[new_state].push_back(state);
                    }
                }
                current.clear();
                swap(current, next);
            }
            return result;
        }
        
        /*** construct the word-change-path-inversely ***/
        void gen_path(unordered_map<string, vector<string>> &father, 
                 vector<string> &path, const string& start, const string& word,
                 vector<vector<string>> &result){
            path.push_back(word);
            if(word==start){
                result.push_back(path);
                /*** why not reverse path directly ? ***/
                reverse(result.back().begin(), result.back().end());
            } else {
                for(const auto &f : father[word]){
                    gen_path(father, path, start, f, result);
                }
            }
            path.pop_back();
        }
        
        unordered_set<string> state_extend(const string &s, string endWord, unordered_set<string> &wordList, unordered_set<string>& visited){
            unordered_set<string> result;
            for(size_t i=0; i<s.size(); i++){
                string new_word(s);
                for(char c='a'; c<='z'; c++){
                    if(c==new_word[i])  continue;
                    swap(c, new_word[i]);
                    if((wordList.find(new_word)!=wordList.end() || new_word==endWord) && 
                           visited.find(new_word)==visited.end()){
                        result.insert(new_word);           
                    }
                    swap(c, new_word[i]);
                }
            }
            return result;
        }
        
        bool state_is_target(const string &s, string end) {
            return s==end;
        }
    };

  • 0
    2

    This is my un-AC implementation , wait for some one to help me to point out the bug ...

    class Solution {
    public:
        vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
            vector<vector<string>> result;
            unordered_map<string, vector<string>> father;
            
            vector<string> cur, next;
            unordered_set<string> visited;
            
            cur.push_back(beginWord);
            
            while(!cur.empty()) {
                for(auto it : cur)  visited.insert(it);
                
                for(auto it : cur) {
                    if(it == endWord) {
                        vector<string> path;
                        generatePath(it, beginWord, path, result, father);
                        //continue;
                    }
                    
                    vector<string> words = generateNext(it, endWord, visited, wordList);
                    for(auto word : words) {
                        next.push_back(word);
                        father[word].push_back(it);
                    }
                }
                cur.clear();
                swap(cur, next);
            }
            return result;
        }
        
        void generatePath(string word, string start, vector<string>& path, vector<vector<string>>& result, unordered_map<string, vector<string>>& father) {
            path.push_back(word);
            
            if(word == start) {
                result.push_back(path);
                reverse(result.back().begin(), result.back().end());
            } else {
                for(auto it : father[word]) {
                    generatePath(it, start, path, result, father);
                }
            }
            path.pop_back();
        }
        
        vector<string> generateNext(string word, string endWord, unordered_set<string>& visited, unordered_set<string>& dict) {
            vector<string> result;
            for(int i = 0; i < word.size(); i++) {
                string next = word;
                for(char c = 'a';  c <= 'z'; c++) {
                    if(c == next[i]) continue;
                    swap(next[i], c);
                    if((dict.find(word)!=dict.end() || word == endWord) && visited.find(word) == visited.end())
                        result.push_back(word);
                    swap(next[i], c);
                }
            }
            return result;
        }
    };

Log in to reply
 

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