127. Word Ladder

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:

• Every adjacent pair of words differs by a single letter.
• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words
in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

• Two-end search BFS solution
• Time : O(nlogn)
• Space : O(n)

c++

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& words) {
        unordered_set<string> w(words.begin(), words.end()), beginQ, endQ, *pBeginQ, *pEndQ;
        if(!w.count(endWord)) return 0;
        beginQ.insert(beginWord);
        endQ.insert(endWord);

        int res = 2;
        while(!beginQ.empty() and !endQ.empty()) {
            if(beginQ.size() <= endQ.size()) {
                *pBeginQ = beginQ;
                *pEndQ = endQ;
            } else {
                *pBeginQ = endQ;
                *pEndQ = beginQ;
            }
            unordered_set<string> tmpQ;
            for(auto& str : *pBeginQ) {
                for(int i = 0; i < str.length(); i++) {
                    string tmp = str;
                    for(int j = 0; j < 26; j++) {
                        tmp[i] = j + 'a';
                        if(pEndQ->count(tmp)) return res;
                        if(w.count(tmp)) {
                            w.erase(tmp);
                            tmpQ.insert(tmp);
                        }
                    }
                }
            }
            tmpQ.swap(*pBeginQ);
            res++;
        }
        return 0;
    }
};

• Time : O(n2)
• Space : O(n)

c++

class Solution {
    bool canModify(string& from, string& to) {
        int cnt = 0;
        for(int i = 0; i < from.length() and cnt <= 1; i++) {
            if(from[i] != to[i]) ++cnt;
        }
        return cnt == 1;
    }
public:
    int ladderLength(string beginWord, string endWord, vector<string>& w) {
        unordered_map<string, vector<string>> gr;
        w.push_back(beginWord);
        for(int i = 0; i < w.size(); i++) {
            for(int j = i + 1; j < w.size(); j++) {
                if(canModify(w[i], w[j])) {
                    gr[w[i]].push_back(w[j]);
                    gr[w[j]].push_back(w[i]);
                }
            }
        }
        
        if(!gr.count(endWord)) return 0;

        queue<string> q;
        unordered_set<string> v;
        q.push(beginWord);
        v.insert(beginWord);
        int res = 2;
        while(!q.empty()) {
            int sz = q.size();
            while(sz--) {
                auto str = q.front(); q.pop();
                for(auto nxt : gr[str]) {
                    if(v.count(nxt)) continue;
                    q.push(nxt);
                    v.insert(nxt);
                    if(nxt == endWord) return res;
                }
            }
            res++;
        }
        return 0;
    }
};