29 ms C++ solution: bi-directional BFS


  • 0
    H
    class Solution {
    public:
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
            if (beginWord.size() != endWord.size()) return 0;
            
            unique_ptr<unordered_set<string>> availWords(new unordered_set<string>);
            unique_ptr<unordered_set<string>> setWordsA(new unordered_set<string>);
            unique_ptr<unordered_set<string>> setWordsB(new unordered_set<string>);
            unique_ptr<unordered_set<string>> setWordsW(new unordered_set<string>);
    
            string tmpWord;
            
            // initialize availWords
            for (const auto &word : wordList) {
                if (word.size() == beginWord.size()) 
                    availWords->insert(word);
            }
            if (availWords->count(endWord)) availWords->erase(endWord);
            else return 0;
            
            // initialize word sets
            setWordsA->insert(beginWord);
            setWordsB->insert(endWord);
            
            // initialize ladder length
            int lenLadder = 2;
            while (!setWordsA->empty()) {
                for (const string curWord : *setWordsA) {
                    for (int i = 0; i < curWord.size(); ++i) {
                        tmpWord = curWord;
                        for (tmpWord[i] = 'a'; tmpWord[i] <= 'z'; ++tmpWord[i]) {
                            if (setWordsB->count(tmpWord)) // if tmpWord in setWordsB, ladder found
                                return lenLadder;
                            else if (!availWords->count(tmpWord)) // if tmpWord not in availWords, skip
                                continue;
                            else { // if tmpWord in availWords, move it to setWordsW
                                availWords->erase(tmpWord);
                                setWordsW->insert(tmpWord);
                            }
                        }
                    }
                }
                setWordsA->clear();
                // swap setWordsA and setWordsW
                setWordsA.swap(setWordsW);
                // swap setWordsA and setWordsB, if |setWordsA| > |setWordsB|
                if (setWordsA->size() > setWordsB->size()) setWordsA.swap(setWordsB);
                // increase ladder length
                ++lenLadder;
            }
            return 0;
        }
    };
    

Log in to reply
 

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