這題給我們一個字串的集合 wordList，並給定一個起始字串與一個結束字串，要我們找出所以從起始字串轉換成結束字串中轉換次數最少的轉換方式，轉換一次只能替換目前字串的其中一個字元並且轉換後的字元必須是在 wordList 中存在的。
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]
Example 2:
Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] Output: [] Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
想法:
這題其實算是在求從 beginWord 到 endWord 的所有最短路徑，把每個 word 都視為是一個圖中的 node，則
若兩個 word 只有一個字元不同表示他們在圖中有邊相連，如此只需要利用 BFS 就可以找出答案！
完整程式碼:
解法一(BFS, 紀錄每個 word 的 parent 方便 backtrace):
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
unordered_set mapping(wordList.begin(), wordList.end());
if (!mapping.count(endWord)) { return {}; }
mapping.erase(beginWord);
mapping.erase(endWord);
// 走到這個字要花多少步
unordered_map<string, int> steps{{beginWord, 1}};
// 每個字的父節點(可以走到/transfer 成該字的所有字)
unordered_map<string, vector<string>> parents;
queue<string> q;
q.push(beginWord);
vector<vector<string>> res;
int step = 0;
bool found = false;
while (!q.empty() && !found) {
++step;
int q_size = q.size();
for (int i = 0; i < q_size; i++) {
const auto cur = q.front();
q.pop();
auto w = cur;
for (int j = 0; j < cur.size(); j++) {
const char ch = w[j];
for (int k = 'a'; k < 'z'; k++) {
if (k == ch) { continue; }
w[j] = k;
if (w == endWord) {
// 由cur transfer 來的
parents[w].push_back(cur);
found = true;
}
else {// 表示有另外一種轉換方式可以在相同步數內轉換到 w if (steps.count(w) && step < steps.at(w)) { parents[w].push_back(cur); } } if (!mapping.count(w)) { continue; } mapping.erase(w); q.push(w); steps[w] = steps.at(cur) + 1; parents[w].push_back(cur); } w[j] = ch; } } } if (found) { vector<string> path({endWord}); backTrace(endWord, beginWord, parents, path, res); } return res; } void backTrace(const string& cur, const string& beginWord, const unordered_map<string, vector<string>>& parents, vector<string>& path, vector<vector<string>>& res) { if (cur == beginWord) { res.push_back(vector<string>(path.rbegin(), path.rend())); return; } // 從終點往前 trace ，因此過程中每個 word 一定會有 parent(不然無法 propagate 到 endWord) for (const auto& p : parents.at(cur)) { path.emplace_back(p); backTrace(p, beginWord, parents, path, res); path.pop_back(); } return; } };
解法二(BFS, 紀錄每個 word 的 children 方便 backtrace):
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
unordered_set mapping(wordList.begin(), wordList.end());
if (!mapping.count(endWord)) { return {}; }
unordered_set<string> q{{beginWord}};
unordered_set<string> p;
unordered_map<string, vector<string>> children;
vector<vector<string>> res;
bool found = false;
while (!q.empty() && !found) {
for (const auto& word : q) {
mapping.erase(word);
}
for (const auto& word : q) {
auto cur = word;
for (int i = 0; i < cur.size(); i++) {
char ch = cur[i];
for (int j = 'a'; j <= 'z'; j++) {
cur[i] = j;
if (cur == endWord) {
found = true;
children[word].emplace_back(cur);
}
else {
// 如果已經 found == true, 表示這個 transfer 已經不可能是最短路徑
if (mapping.count(cur) && !found) {
// 加入下一步要propagate 的 queue
p.insert(cur);
children[word].emplace_back(cur);
}
}
}
cur[i] = ch;
}
}
swap(q, p);
// 沒 clear 的話 q 會一直增長 (會把已經propagate過的點一直加進來)
p.clear();
}
if (found) {
vector<string> cur{beginWord};
backTrace(beginWord, endWord, children, res, cur);
}
return res;
}
void backTrace(const string& curWord, const string& endWord, const unordered_map<string, vector<string>>& children, vector<vector<string>>& res, vector<string> cur) {
if (curWord == endWord) {
res.emplace_back(cur);
return;
}
// 因為是紀錄 children，有些非最短路徑上的 word 並不會繼續 propagate 因此不一定有 child。ex: begin: a, end: c, wordList:{a, b,c}，因為 b 會在 c 前面被 a propagate 到但 a->b->c 並非最短路徑，b 並不會繼續 propagate，因此 b 沒有 child。
if (children.find(curWord) == children.end()) { return; }
for (const auto& child : children.at(curWord)) {
cur.emplace_back(child);
backTrace(child, endWord, children, res, cur);
cur.pop_back();
}
return;
}
};解法三(Bidirectional BFS, 從 beginWord 與 endWord 同時 propagate):
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> mapping(wordList.begin(), wordList.end());
if (!mapping.count(endWord)) { return {}; }
unordered_set<string> q1{{beginWord}};
unordered_set<string> q2{{endWord}};
unordered_map<string, vector<string>> parents;
vector<vector<string>> res;
bool found = false;
bool backward = false;
while (!q1.empty() && !q2.empty() && !found) {
if (q1.size() > q2.size()) {
swap(q1, q2);
backward = !backward;
}
for (const string& word : q1) {
mapping.erase(word);
}
for (const string& word : q2) {
mapping.erase(word);
}
unordered_set<string> q;
for (const string& word : q1) {
string cur = word;
for (int i = 0; i < cur.size(); i++) {
const char ch = cur[i];
for (int j = 'a'; j <= 'z'; j++) {
cur[i] = j;
const string* parent = &word;
const string* child = &cur;
if (backward) {
swap(parent, child);
}
if (q2.count(cur)) {
found = true;
parents[*child].emplace_back(*parent);
}
else if (mapping.count(cur) && !found) {
q.insert(cur);
parents[*child].emplace_back(*parent);
}
}
cur[i] = ch;
}
}
swap(q1, q);
}
if (found) {
vector<string> cur{endWord};
backTrace(endWord, beginWord, parents, res, cur);
}
return res;
}
void backTrace(const string& curWord, const string& beginWord, const unordered_map<string, vector<string>>& parents, vector<vector<string>>& res, vector<string>& cur) {
if (curWord == beginWord) {
res.emplace_back(vector<string>(cur.rbegin(), cur.rend()));
return;
}
// 有些點在過程中因為不是最短路徑並不會 propagate 到最後，因此不一定有 parents.
if (parents.find(curWord) == parents.end()) { return; }
for (const string& parent : parents.at(curWord)) {
cur.emplace_back(parent);
backTrace(parent, beginWord, parents, res, cur);
cur.pop_back();
}
return;
}
};
沒有留言:
張貼留言