For this problem, we can build the graph in two ways:

1. Graph A: Check all posible pair of string to see whether they have distance of 1 and build the graph.
2. Graph B: Change one character of the word to a new word and check whether the new word in unexplored word list.
`class Solution {public:    string end;    int len = INT_MAX;    bool disOne(string a, string b){        int cnt = 0;        for (int i = 0; i < a.size(); ++i){            cnt += a[i] != b[i];            if (cnt > 1) return false;        }        return cnt == 1;    }   void backtrack(string curr,  unordered_map<string, vector<string>> &graph, vector<string> history,  vector<vector<string>>& ret, unordered_set<string>& seen){        history.push_back(curr);        if (curr == end){            ret.push_back(history);            len = min(len, (int)history.size());            return;        }         if (history.size() >= len)return;        for (auto w: graph[curr]){            if (seen.find(w) == seen.end()) {                seen.insert(w);                backtrack(w, graph, history, ret, seen);                seen.erase(w);            }        }            }    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {        const int n = wordList.size();        end = endWord;        // build graph        unordered_map<string, vector<string>> graph;        for (int i = 0; i < n - 1; ++i){            for (int j = i + 1; j < n; ++j){                if (disOne(wordList[i], wordList[j])){                    graph[wordList[i]].push_back(wordList[j]);                    graph[wordList[j]].push_back(wordList[i]);                }            }        }        auto it = find(wordList.begin(), wordList.end(), beginWord);       if (it == wordList.end()){            for (auto word: wordList) if (disOne(beginWord, word))graph[beginWord].push_back(word);        }        vector<vector<string>> ret;        string curr = beginWord;        vector<string> history;        unordered_set<string> seen;        seen.insert(beginWord);        backtrack(curr, graph, history, ret, seen);        sort(ret.begin(), ret.end(), [](vector<string> &a, vector<string> &b){            return a.size() < b.size();        });        if (ret.empty()) return ret;        int minSz = (*ret.begin()).size();        vector<vector<string>> finret;        for (auto r: ret){            if (r.size() == minSz) finret.push_back(r);        }        return finret;            }};`
`class Solution {    public:    string end;    int len = INT_MAX;    bool disOne(string a, string b){        int cnt = 0;        for (int i = 0; i < a.size(); ++i){            cnt += a[i] != b[i];            if (cnt > 1) return false;        }        return cnt == 1;    }    void bfs(string curr,  unordered_map<string, vector<string>> &graph,  vector<vector<string>>& ret, unordered_set<string> seen){                vector<vector<string>> currentlevel;        currentlevel.push_back(vector<string>{curr});        bool found = false;        unordered_set<string> newseen;        while (currentlevel.size() && !found){            vector< vector<string>> nextlevel;            newseen = seen;            for (auto& vec: currentlevel){                for (auto s: graph[vec.back()]){                    vector<string> thisvec = vec;                    if (seen.find(s) == seen.end() || s == end){                        newseen.insert(s);                        thisvec.push_back(s);if (s == end) {                            found = true;                            ret.push_back(thisvec);                            continue;                        }                        nextlevel.push_back(thisvec);                    }                }            }            currentlevel = nextlevel;            seen = newseen;        }    }    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {         vector<vector<string>> ret;        if (find(wordList.begin(), wordList.end(), endWord) == wordList.end())return ret;        const int n = wordList.size();        end = endWord;        // build graph        unordered_map<string, vector<string>> graph;        for (int i = 0; i < n - 1; ++i){            for (int j = i + 1; j < n; ++j){                if (disOne(wordList[i], wordList[j])){                    graph[wordList[i]].push_back(wordList[j]);                    graph[wordList[j]].push_back(wordList[i]);                }            }        }        auto it = find(wordList.begin(), wordList.end(), beginWord);        if (it == wordList.end()){            for (auto word: wordList) if (disOne(beginWord, word))graph[beginWord].push_back(word);        }               unordered_set<string> seen;        seen.insert(beginWord);        bfs(beginWord, graph, ret, seen);        return ret;    }};`

runtime

`Runtime: 36 ms, faster than 23.18% of C++ online submissions for Word Ladder II.Memory Usage: 19.8 MB, less than 10.99% of C++ online submissions for Word Ladder II.`
`class Solution {    public:    string end;    //int len = INT_MAX;    vector<string> wordList;    bool disOne(int i, int j){        int cnt = 0;        //cout << wordList.size()<<endl;        auto a = wordList[i], b = wordList[j];        for (int k = 0; k < a.size(); ++k){            cnt += a[k] != b[k];            if (cnt > 1) return false;        }        return cnt == 1;    }    void bfs(int curr,  vector<vector<int>> &graph,  vector<vector<int>>& ret, unordered_set<int> seen){        vector<vector<int>> currentlevel;        currentlevel.push_back(vector<int>{curr});        bool found = false;        unordered_set<int> newseen;        while (currentlevel.size() && !found){            vector< vector<int>> nextlevel;            newseen = seen;            for (auto& vec: currentlevel){                for (auto s: graph[vec.back()]){                    vector<int> thisvec = vec;                    if (seen.find(s) == seen.end() || wordList[s] == end){                        newseen.insert(s);                        thisvec.push_back(s);if (wordList[s] == end) {                            found = true;                            ret.push_back(thisvec);                            continue;                        }                        nextlevel.push_back(thisvec);                    }                }            }            currentlevel = nextlevel;            seen = newseen;        }    }    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {        const int n = wordList.size();        vector<vector<int>> ret;        if (find(wordList.begin(), wordList.end(), endWord) == wordList.end()) return {};        end = endWord;        int root = -1;        // build graph        wordList.push_back(beginWord);        this -> wordList = wordList;        vector<vector<int>> graph(n+1);        for (int i = 0; i < n - 1; ++i){             if (wordList[i] == beginWord) root = i;            for (int j = i + 1; j < n; ++j){                auto good = disOne(i, j);                if (good){                    graph[i].push_back(j);                    graph[j].push_back(i);                }            }        }        if (root == -1){            root = n;            for (int i =0; i < n; ++i) if (disOne(i, n))graph[n].push_back(i);        }                      unordered_set<int> seen;        seen.insert(root);        bfs(root, graph, ret, seen);        vector<vector<string>> finret;        for (auto r: ret){            vector<string> thisone;            for (int i: r) thisone.push_back(wordList[i]);            finret.push_back(thisone);        }        return finret;    }};`

runtime

`Runtime: 32 ms, faster than 26.20% of C++ online submissions for Word Ladder II.Memory Usage: 11.3 MB, less than 39.62% of C++ online submissions for Word Ladder II.`

The following python code can get AC, the key idea is changing each character to construct a new word. Once the new word is in the unexplored word set, then explore this node. Seems this one is pretty fast.

`class Solution:    def findLadders(self, begin: str, end: str, wordList: List[str]) -> List[List[str]]:        res = []        def bfs(begin):            word_set = set(wordList)            level = [(begin, begin)]            found = False            while level and not found:                new_level = []                for word, hist in level:                          for i in range(len(word)):                        for new_c in "abcdefghijklmnopqrstuvwxyz":                            new_word = word[:i]+new_c+word[i+1:]                            if new_word in word_set:                                if new_word == end:                                    found = True                                    res.append(hist+","+new_word)                                else:                                    new_level.append((new_word, hist+','+new_word))                word_set-={w for w, _ in new_level}                level = new_level        bfs(begin)        return [r.split(',') for r in res] if res else []`

Run time

`Runtime: 88 ms, faster than 33.78% of Python3 online submissions forWord Ladder II.Memory Usage: 14.5 MB, less than 87.41% of Python3 online submissions for Word Ladder II.`
`class Solution {    public:    string end;    void bfs(string word, unordered_set<string>& words,vector<vector<string>>& ret ){        vector<vector<string>> level;        if (words.find(end) == words.end())return;        level.push_back(vector<string>{word});        bool done = false;        while (!level.empty() && !done){            vector<vector<string>> newLevel;            unordered_set<string> seen;            for (auto vec: level){                string lastWord = vec.back();                for (int i = 0; i < lastWord.size(); ++i){                    for (char c = 'a'; c <= 'z'; ++c){                        if (c == lastWord[i]) continue;                        string newWord = lastWord;                         newWord[i] = c;                        if (newWord == end){                            done = true;                            vector<string> newvec(vec.begin(), vec.end());                            newvec.push_back(newWord);                            ret.push_back(newvec);                            continue;                        }                         if (words.find(newWord) != words.end()){                            seen.insert(newWord);                            vector<string> newvec = vec;                            newvec.push_back(newWord);                            newLevel.push_back(newvec);                        }                    }                }            }            for (auto w: seen) words.erase(w);            level = newLevel;        }}    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {        end = endWord;        unordered_set<string> words(wordList.begin(), wordList.end());        vector<vector<string>> ret;        bfs(beginWord, words, ret);        return ret;    }};`

Runtime

`Runtime: 20 ms, faster than 44.90% of C++ online submissions for Word Ladder II.Memory Usage: 12.9 MB, less than 19.36% of C++ online submissions for Word Ladder II.`

The complexity of this algorithm should be O(26*n*k) where n is the wordList size and k is the beginWord size. maximum n is 1000 and maximum k is 5. So the total complexity is O(26*1000*5) = O(130K)

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi