Problem:
Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
- Only one letter can be changed at a time
- Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Return
|
1 2 3 4 |
[ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ] |
Note:
- Return an empty list if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
- You may assume no duplicates in the word list.
- You may assume beginWord and endWord are non-empty and are not the same.
Idea:
BFS to construct the graph + DFS to extract the paths
Solutions:
C++, BFS 1
|
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 |
// Author: Huahua // Running Time: 216 ms (better than 65.42%) class Solution { public: vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) { unordered_set<string> dict(wordList.begin(), wordList.end()); if (!dict.count(endWord)) return {}; dict.erase(beginWord); dict.erase(endWord); unordered_map<string, int> steps{{beginWord, 1}}; unordered_map<string, vector<string>> parents; queue<string> q; q.push(beginWord); vector<vector<string>> ans; const int l = beginWord.length(); int step = 0; bool found = false; while (!q.empty() && !found) { ++step; for (int size = q.size(); size > 0; size--) { const string p = q.front(); q.pop(); string w = p; for (int i = 0; i < l; i++) { const char ch = w[i]; for (int j = 'a'; j <= 'z'; j++) { if (j == ch) continue; w[i] = j; if (w == endWord) { parents[w].push_back(p); found = true; } else { // Not a new word, but another transform // with the same number of steps if (steps.count(w) && step < steps.at(w)) parents[w].push_back(p); } if (!dict.count(w)) continue; dict.erase(w); q.push(w); steps[w] = steps.at(p) + 1; parents[w].push_back(p); } w[i] = ch; } } } if (found) { vector<string> curr{endWord}; getPaths(endWord, beginWord, parents, curr, ans); } return ans; } private: void getPaths(const string& word, const string& beginWord, const unordered_map<string, vector<string>>& parents, vector<string>& curr, vector<vector<string>>& ans) { if (word == beginWord) { ans.push_back(vector<string>(curr.rbegin(), curr.rend())); return; } for (const string& p : parents.at(word)) { curr.push_back(p); getPaths(p, beginWord, parents, curr, ans); curr.pop_back(); } } }; |
C++ / BFS 2
|
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 |
// Author: Huahua // Running time: 129 ms (better than 80.67%) class Solution { public: vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) { vector<vector<string>> ans; unordered_set<string> dict(wordList.begin(), wordList.end()); if (!dict.count(endWord)) return ans; dict.erase(endWord); const int l = beginWord.length(); unordered_set<string> q{beginWord}, p; unordered_map<string, vector<string>> children; bool found = false; while (!q.empty() && !found) { for (const string& word : q) dict.erase(word); for (const string& word : q) { string curr = word; for (int i = 0; i < l; i++) { char ch = curr[i]; for (int j = 'a'; j <= 'z'; j++) { curr[i] = j; if (curr == endWord) { found = true; children[word].push_back(curr); } else if (dict.count(curr) && !found) { p.insert(curr); children[word].push_back(curr); } } curr[i] = ch; } } std::swap(p, q); p.clear(); } if (found) { vector<string> path{beginWord}; getPaths(beginWord, endWord, children, path, ans); } return ans; } private: void getPaths(const string& word, const string& endWord, const unordered_map<string, vector<string>>& children, vector<string>& path, vector<vector<string>>& ans) { if (word == endWord) { ans.push_back(path); return; } const auto it = children.find(word); if (it == children.cend()) return; for (const string& child : it->second) { path.push_back(child); getPaths(child, endWord, children, path, ans); path.pop_back(); } } }; |
C++ / Bidirectional BFS
|
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 |
// Author: Huahua // Running time: 39 ms (better than 93.74%) class Solution { public: vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) { vector<vector<string>> ans; unordered_set<string> dict(wordList.begin(), wordList.end()); if (!dict.count(endWord)) return ans; int l = beginWord.length(); unordered_set<string> q1{beginWord}; unordered_set<string> q2{endWord}; unordered_map<string, vector<string>> children; bool found = false; bool backward = false; while (!q1.empty() && !q2.empty() && !found) { // Always expend the smaller queue first if (q1.size() > q2.size()) { std::swap(q1, q2); backward = !backward; } for (const string& w : q1) dict.erase(w); for (const string& w : q2) dict.erase(w); unordered_set<string> q; for (const string& word : q1) { string curr = word; for (int i = 0; i < l; i++) { char ch = curr[i]; for (int j = 'a'; j <= 'z'; j++) { curr[i] = j; const string* parent = &word; const string* child = &curr; if (backward) std::swap(parent, child); if (q2.count(curr)) { found = true; children[*parent].push_back(*child); } else if (dict.count(curr) && !found) { q.insert(curr); children[*parent].push_back(*child); } } curr[i] = ch; } } std::swap(q, q1); } if (found) { vector<string> path{beginWord}; getPaths(beginWord, endWord, children, path, ans); } return ans; } private: void getPaths(const string& word, const string& endWord, const unordered_map<string, vector<string>>& children, vector<string>& path, vector<vector<string>>& ans) { if (word == endWord) { ans.push_back(path); return; } const auto it = children.find(word); if (it == children.cend()) return; for (const string& child : it->second) { path.push_back(child); getPaths(child, endWord, children, path, ans); path.pop_back(); } } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment