A simple yet best solution in C++


  • 3
    class Solution
    {
        public:
            //AC - 59ms;
            int ladderLength(string bWord, string eWord, unordered_set<string>& wordList)
            {
                if(bWord == eWord) return 1;
                unordered_set<string> bList, eList;
                bList.insert(bWord);
                eList.insert(eWord);
                wordList.erase(bWord);
                wordList.erase(eWord);
                int len = 1;
                while(!bList.empty()&&!eList.empty())
                {
                    if(bList.size() > eList.size()) bList.swap(eList);
                    unordered_set<string> tmpList;
                    for(auto cur: bList) //access by value, it will be copied;
                    {
                        for(auto &c: cur) //access by reference, it will be directly accessed;
                        {
                            char c0 = c;
                            for(c = 'a'; c <= 'z'; c++)
                            {
                                if(c != c0) //avoid invalid further checking;
                                {
                                    if(eList.count(cur)) return len+1;
                                    if(wordList.count(cur)) //build up intermediate set and removing noise;
                                    {
                                        tmpList.insert(cur);
                                        wordList.erase(cur);
                                    }
                                }
                            }
                            c = c0;
                        }
                    }
                    bList.swap(tmpList); //update bList;
                    len++;
                }
                return 0;
            }
    };

Log in to reply
 

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