Share the vector version of two-end BFS in c++ 32ms


  • 4
    A
    class Solution {
    public:
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
            unordered_set<string> beginlist;
            unordered_set<string> endlist;
            unordered_set<string> rest;
            for(int i=0;i<wordList.size();i++) rest.insert(wordList[i]);
            if (rest.find(endWord) != rest.end()) {
                rest.erase(endWord);
            }else{
                return 0;
            }
            int depth = 2;
            beginlist.insert(beginWord);
            endlist.insert(endWord);
            while(!beginlist.empty() && !endlist.empty()){
                unordered_set<string> * pb;
                unordered_set<string> * pe;
                if (beginlist.size() < endlist.size()) {
                    pb = &beginlist; 
                    pe = &endlist; 
                } else {
                    pe = &beginlist; 
                    pb = &endlist; 
                }
                unordered_set<string> tmp;
                for(unordered_set<string>::iterator it = pb->begin();it!=pb->end();it++){
                    string w = *it;
                    for(int i=0;i<w.length();i++)
                    {
                        char c = w[i];
                        for(int j=0;j<26;j++)
                        {
                            w[i] = 'a'+j;
                            if (w[i] == c) continue;
                            // printf("%s\n", w.c_str());
                            if (pe->find(w) != pe->end()) {
                                // printf("now find %s in pe.\n", w.c_str());
                                return depth;
                            }
                            if (rest.find(w) != rest.end()) {
                                tmp.insert(w);
                                rest.erase(w);
                            }
                        }
                        w[i] = c;
                    }
                }
                depth++;
                *pb = tmp;
            }
            return 0;
        }
    };
    

    ···


  • 0
    K

    Cool solution! But I can'tunderstand. Could you make some explaination with those codes.Thank you very much.


Log in to reply
 

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