problem:
一道模拟题,用深搜匹配一下所有情况即可。
class Solution { public: vector<vector<unordered_set<char>>> pair; bool dfs(string cur, string next, int i) { if(cur.empty()) return true; // 搜到顶层了,返回true for(int j = i;j < cur.size();j++) { unordered_set<char>& candidate = pair[cur[j - 1] - 'A'][cur[j] - 'A']; if(candidate.size() == 0) return false; if(candidate.size() == 1) // 只有一种选择,就直接选了 { next.push_back(*candidate.begin()); } else { for(auto& ch : candidate) // 有多种选择,就每个都试一下 { if(dfs(cur, next + ch, j + 1)) { return true; } } return false; } } return dfs(next, "", 1); // 搜索下一层 } bool pyramidTransition(string bottom, vector<string>& allowed) { pair.resize(8, vector<unordered_set<char>>(8)); for(int i = 0;i < allowed.size(); i++) { pair[allowed[i][0] - 'A'][allowed[i][1] - 'A'].insert(allowed[i][2]); } return dfs(bottom, "", 1); } };