https://leetcode.com/problems/pyramid-transition-matrix/submissions/1868719957
終於寫到一題有難度的 medium 了！！這一題若是沒有看過，光理解題目就要花點時間了。
理解題目後我第一時間想到的做法是 recursive：每一個 level 的 block 都去遍歷所有可能性的下一個 level 組合。看起來有點饒口，簡單來說就是每個 level 先找出所有上一層的可能性組合，這裡要透過 allowed 來做比對。找到後去一個一個的 recursive 繼續找，就是 DFS + DP 的做法。
想法很快就有了，但構建程式碼過程真的是很痛苦，畢竟 recursive 的程式碼本就容易寫錯。好不容易寫完後卻是有幾筆測資 TLE，才發現太多相似的 pattern 會被重複做 recursive，在我的做法裡這非常得耗時，因此我們需要適當的剪枝。我用的方式也沒啥特別的就是用 map，參考他的 input 規範，用 map 應該是還不會爆。
anyway 這一題 AC 真是困難重重，花了兩三個小時，最後拿到 beat 42% 的成績（memory 更是慘不忍睹這邊不提QQ）。感覺演算法的部分跟別人大差不差，之後再來看看別人都做了些啥。
class Solution {
public:
bool pyramidTransition(string bottom, vector<string>& allowed) {
map<string, string> allowedMap;
map<string, int> flagMap;
for (int i = 0; i < allowed.size(); i++) {
string temp = "";
temp.assign(allowed[i], 0, 2);
allowedMap[temp] += allowed[i][2];
}
return RecurStack(bottom, allowed, allowedMap, flagMap);
}
bool RecurStack(string bottom, vector<string>& allowed, map<string, string>& allowedMap, map<string, int>& flagMap){
if(bottom.length() == 2){
auto iter = flagMap.find(bottom);
if(iter != flagMap.end())
return false;
vector<string> allNextBottomVector;
allNextBottomVector = allNextBottomCombination(bottom, allowed, allowedMap);
if (allNextBottomVector.empty()) {
flagMap[bottom] = 0;
return false;
}
return true;
}
else {
vector<string> allNextBottomVector;
allNextBottomVector = allNextBottomCombination(bottom, allowed, allowedMap);
if (allNextBottomVector.empty()) return false;
for (auto bot: allNextBottomVector) {
auto iter = flagMap.find(bot);
if(iter != flagMap.end()) continue;
if (RecurStack(bot, allowed, allowedMap, flagMap) == true) return true;
flagMap[bot] = 0;
}
return false;
}
}
vector<string> allNextBottomCombination(string bottom, vector<string>& allowed, map<string, string>& allowedMap) {
vector<string> allNextBottomCombination;
string temp_str;
vector<string> temp_vec;
temp_vec.push_back("");
for (int i = 0; i < bottom.length() - 1; i++) {
temp_str = "";
temp_str.assign(bottom, i, 2);
auto iter = allowedMap.find(temp_str);
if(iter != allowedMap.end()) {
for (int j = 0; j < iter->second.length(); j++) {
for (int k = 0; k < temp_vec.size(); k++) {
if (allNextBottomCombination.size() < k + j * temp_vec.size() + 1) {
allNextBottomCombination.push_back("");
}
allNextBottomCombination[k + j * temp_vec.size()] = temp_vec[k] + iter->second[j];
}
}
temp_vec = allNextBottomCombination;
}
else {
vector<string> dummy;
return dummy;
}
}
return allNextBottomCombination;
}
};
Best Solution
不想看解釋的可以直接讀 code，個人認為可讀性很高（自己說）
總而言之結合了討論區還有 gmeini 的建議，我把程式碼改寫成了如下。主要有兩個優化的地方：
第一個是改用 bitset。上過程式基礎課程的人一定都知道用 bit 的操作會遠遠大於用其他的資料型態，但偏偏 bit 的使用不那麼直覺。看了別人的寫法猶如醍醐灌頂，原來這就是刷題的真諦。
第二個是改用徹底的 DFS。原本的做法其實有點四不像，雖然有 DFS 的影子，卻還要用大量的時間去 search 下一步的所有可能性。這點很可惜，因為我到最後都在思考要如何優化這邊，可惜試了一下還是放棄思考了直接看解答。
class Solution {
int patterns[6][6];
unordered_set<string> failed;
public:
bool pyramidTransition(string bottom, vector<string>& allowed) {
memset(patterns, 0, sizeof(patterns));
failed.clear();
for (const string& s : allowed) {
patterns[s[0] - 'A'][s[1] - 'A'] |= (1 << (s[2] - 'A'));
}
return solve(bottom, "");
}
bool solve(string& bottom, string next) {
if (bottom.length() == 1)
return true;
if (next.length() == bottom.length() - 1) {
if (failed.count(next))
return false;
if (solve(next, ""))
return true;
failed.insert(next);
return false;
}
int left = bottom[next.length()] - 'A';
int right = bottom[next.length() + 1] - 'A';
int mask = patterns[left][right];
for (int i = 0; i < 6; ++i) {
if (mask & (1 << i)) {
if (solve(bottom, next + (char)('A' + i))) {
return true;
}
}
}
return false;
}
};
刷了四題下來唯一我有去看討論區的，目前感想是 leetcode 很多這種好題目（燒腦），但也很多跟標示難度不一的題目。除此之外也是把一些平常沒在用的優化技巧撿回來（像是這次的 bitset）。已經很久沒有過這種每一個計算都要斤斤計較的程式撰寫過程了，大學後期我修到的課基本上只在乎有沒有做出來的結果論，不在乎效能那些。因為當時想逃避這種天才怪物最多的課程哈哈哈，在 leetcode 終究還是要還（笑著說）。
