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].
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 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) { 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) { 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; } };