126. Word Ladder II

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 all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, …, sk].

c++

class Solution {
    unordered_map<string, vector<string>> g;
    unordered_set<string> c;
    int len = INT_MAX;
    vector<vector<string>> res;
    bool similar(string& s1, string& s2) { //o(k)
        int diff = 0;
        for(int i = 0; i < s1.length() and diff < 2; i++) {
            if(s1[i] != s2[i]) diff++;
        }
        return diff == 1;
    }
    
    void buildG(vector<string>& w, string& begin) { //o(n^2)
        for(int i = 0; i < w.size(); i++) {
            for(int j = i + 1; j < w.size(); j++) {
                if(similar(w[i], w[j])) {
                    g[w[i]].push_back(w[j]);
                    g[w[j]].push_back(w[i]);
                }
            }
        }
        if(!g.count(begin)) {
            for(int i = 0; i < w.size(); i++) {
                if(similar(begin,w[i])) 
                    g[begin].push_back(w[i]);
            }
        }
    }
    void backTracking(string& cur, string& target, vector<string>& tmp) {
        if(tmp.size() > len) return;
        if(tmp.back() == target) {
            if(tmp.size() < len) {
                len = tmp.size();
                res.clear();
            }
            res.push_back(tmp);
            return;
        }
        
        for(auto nxt : g[cur]) {
            if(c.count(nxt)) continue;
            c.insert(nxt);
            tmp.push_back(nxt);
            backTracking(nxt, target, tmp);
            tmp.pop_back();
            c.erase(nxt);
        }
    }
    void insert(unordered_map<string,int>& m, string& t) {
        vector<string> ans(m.size() + 1);
        ans[m.size()] = t;
        for(auto [k, i] : m) {
            ans[i] = k;
        }
        res.push_back(ans);
    }
    void bfs(string& st, string& t) {
        queue<vector<string>> q;
        unordered_set<string> v{st};
        q.push({st});
        while(res.empty()) {
            int sz = q.size();
            unordered_set<string> lv;
            while(sz--) {
                auto vec = q.front(); q.pop();
                for(auto nxt : g[vec.back()]) {
                    if(v.count(nxt)) continue;
                    if(nxt == t) {
                        vec.push_back(nxt);
                        res.push_back(vec);
                        break;
                    } else {
                        lv.insert(nxt);
                        vec.push_back(nxt);
                        q.push(vec);
                        vec.pop_back();
                    }
                }
            }
            v.insert(lv.begin(),lv.end());
        }
    }
    
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        buildG(wordList, beginWord);
        if(!g.count(endWord)) return res;
        vector<string> tmp{beginWord};
        c.insert(beginWord);
        bfs(beginWord, endWord);
        
        return res;
    }
};