52 ms C++ solution with 18 lines only


  • 4
    G

    two-end BFS + hash table

    class Solution {
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
            unordered_set<string> head({ beginWord }), tail({ endWord }), next;
            int dist = 2, size = beginWord.size();
            while (!head.empty()) {
                for (auto& h : head) wordList.erase(h);
                for (auto src : head) {
                    for (int i = 0; i<size; ++i) {
                        char tmp = src[i];
                        for (src[i] = 'a'; src[i] <= 'z'; ++src[i]) {
                            auto it = wordList.find(src);
                            if (it != wordList.end()) {
                                if (tail.find(*it) != tail.end()) return dist;
                                next.insert(*it);
                            }
                        }
                        src[i] = tmp;
                    }
                }
                ++dist;
                head.swap(next);
                next.clear();
                if (head.size()>tail.size()) head.swap(tail);
            }
            return 0;
        }
    };
    

Log in to reply
 

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