35 Lines of Simple C++ Code - Traditional BFS


  • 0
    S
    vector<string> findOneDistWords(string str, unordered_set<string>& wordList) {
            int N = str.length();
            vector<string> res;
            for(int i = 0; i<N; ++i){
                char oldChar = str[i];
                for(char c = 'a'; c <= 'z'; c++) {
                    str[i] = c;
                    if (wordList.find(str) != wordList.end()) {
                        res.push_back(str);
                        wordList.erase(str);
                    }
                }
                str[i] = oldChar;
            }
            return res;
        }
        
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
            wordList.insert(endWord);
            queue<string> q;
            q.push(beginWord);
            int level = 0;
            
            while(!q.empty()) {
                int sz = q.size();
                ++level;
                for(int i = 0; i < sz; ++i) {
                    string curr = q.front(); q.pop();
                    if (curr.compare(endWord) == 0) return level;
                    for(auto it : findOneDistWords(curr, wordList)) {
                        q.push(it);
                    }
                }
            }
            return 0;
        }
    

Log in to reply
 

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