56ms c++ solution, two-end bfs, easy understanding


  • 0
    W
    class Solution {
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
            wordList.insert(beginWord);
            wordList.insert(endWord);
            unordered_map<string, int> wordIdx;
            int n = 0;
            for (unordered_set<string>::iterator iter = wordList.begin(); iter != wordList.end(); ++ iter) {
                wordIdx[*iter] = n++;
            }
            queue<string> beginQueue;
            queue<string> endQueue;
            vector<int> beginLen(n, INT_MAX);
            vector<int> endLen(n, INT_MAX);
            beginLen[wordIdx[beginWord]] = 0;
            if (beginLen[wordIdx[endWord]] == 0) {
                return 1;
            } 
            endLen[wordIdx[endWord]] = 0;
            beginQueue.push(beginWord);
            endQueue.push(endWord);
            while (!beginQueue.empty() && !endQueue.empty()) {
                string w = beginQueue.front();
                beginQueue.pop();
                int widx = wordIdx[w];
                for (int i = 0; i < w.size(); ++i) {
                    char wi = w[i];
                    for (char j = 'a'; j < 'z'; ++j) {
                        if (j != wi) {
                            w[i] = j;
                            if (wordIdx.find(w) != wordIdx.end()) {
                                int idx = wordIdx[w];
                                if (beginLen[idx] == INT_MAX) {
                                    beginLen[idx] = beginLen[widx] + 1;
                                    beginQueue.push(w);
                                    if (endLen[idx] != INT_MAX) {
                                        return endLen[idx] + beginLen[idx] + 1;
                                    }
                                }
                            }
                        }
                    }
                    w[i] = wi;
                }
                w = endQueue.front();
                endQueue.pop();
                widx = wordIdx[w];
                for (int i = 0; i < w.size(); ++i) {
                    char wi = w[i];
                    for (char j = 'a'; j < 'z'; ++j) {
                        if (j != wi) {
                            w[i] = j;
                            if (wordIdx.find(w) != wordIdx.end()) {
                                int idx = wordIdx[w];
                                if (endLen[idx] == INT_MAX) {
                                    endLen[idx] = endLen[widx] + 1;
                                    endQueue.push(w);
                                    if (beginLen[idx] != INT_MAX) {
                                        return endLen[idx] + beginLen[idx] + 1;
                                    }
                                }
                            }
                        }
                    }
                    w[i] = wi;
                }
            }
        
            return 0;
        }
    };

Log in to reply
 

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