Quite neat solution yet beating 95% submissions in C++


  • 3

    The current accepted time is 60ms but if we remove this line

    if(forward.size() > backward.size()) backward.swap(forward);

    it will dramatically fall back to 336ms, what a story!

    B.T.W. if we do not erase the words in the backward from wordList, we can further accelerate this solution to 56ms. Little bit weird here.


    class Solution {
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) 
        {
            if(beginWord == endWord) return 2;
            int depth = 1;
            unordered_set<string> forward, backward;
            forward.insert(beginWord);
            backward.insert(endWord);
            while(!forward.empty())
            {
                unordered_set<string> nextLevel;
                for(auto& w: forward) wordList.erase(w);
                for(auto& w: backward) wordList.erase(w);
                for(auto& word: forward)
                {
                    string cur(word);
                    for(auto& c: cur)
                    {
                        char c0 = c;
                        for(c = 'a'; c <= 'z'; ++c)
                        {
                            if(c != c0)
                            {
                                if(backward.count(cur)) return depth+1;
                                if(wordList.count(cur)) nextLevel.insert(cur);
                            }
                        }
                        c = c0;
                    }
                }
                depth++;
                forward.swap(nextLevel);
                if(forward.size() > backward.size()) backward.swap(forward);
            }
            return 0;
        }
    };

  • 0
    Y

    @LHearen Best solution so far, the swap is important!


  • 0
    Y

    Btw, I think if(c != c0) is not necessary since you have checked this word last round and erased it from wordList.


  • 0

    @Yuanhui This will avoid checking instead of necessary accelerating the constructing process actually.


Log in to reply
 

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