题目描述
现在,我们用一些方块来堆砌一个金字塔。每个方块用仅包含一个字母的字符串表示。
使用三元组表示金字塔的堆砌规则如下:
(A, B, C)
表示,C
为顶层方块,方块 A
、B
分别作为方块 C
下一层的的左、右子块。当且仅当 (A, B, C)
是被允许的三元组,我们才可以将其堆砌上。
初始时,给定金字塔的基层 bottom
,用一个字符串表示。一个允许的三元组列表 allowed
,每个三元组用一个长度为 3 的字符串表示。
如果可以由基层一直堆到塔尖返回 true
,否则返回 false
。
样例
输入:bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
输出:true
解释:
可以堆砌成这样的金字塔:
A
/ \
G E
/ \ / \
B C D
因为符合 BCG、CDE 和 GEA 三种规则。
输入:bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
输出:false
解释:
无法一直堆到塔尖。
注意, 允许存在像 ABC 和 ABD 这样的三元组,其中 C != D。
提示
bottom
的长度范围在[2, 8]
。allowed
的长度范围在[0, 200]
。- 方块的标记字母范围为
{'A', 'B', 'C', 'D', 'E', 'F', 'G'}
。
算法
(暴力枚举,哈希表)
- 从最底层开始,暴力拓展出所有可能的上一层的字符串,并逐一递归判断这些字符串的可行性。
- 判断过程中,可以通过哈希表进行加速。
C++ 代码
class Solution {
private:
unordered_set<char> h[7][7];
unordered_set<string> seen;
vector<string> make_candidates(const string &s) {
const int n = s.size();
vector<string> candidates;
candidates.push_back("");
for (int i = 0; i < n - 1; i++) {
vector<string> new_candidates;
for (const string &cand : candidates)
for (char c : h[s[i] - 'A'][s[i + 1] - 'A'])
new_candidates.push_back(cand + c);
candidates = new_candidates;
}
return candidates;
}
bool solve(const string &s) {
if (s.size() == 1)
return true;
if (seen.find(s) != seen.end())
return false;
seen.insert(s);
vector<string> candidates = make_candidates(s);
for (const string &cand : candidates)
if (solve(cand))
return true;
return false;
}
public:
bool pyramidTransition(string bottom, vector<string>& allowed) {
for (const auto &p : allowed)
h[p[0] - 'A'][p[1] - 'A'].insert(p[2]);
return solve(bottom);
}
};
现在过不了了,
Wrong Answer:
input:”AAAA”
[“AAB”,”AAC”,”BCD”,”BBE”,”DEF”]
Output:true
Expected:false
问题主要是在于,比如很高的上层可以合成某个字母比如A,但是他必须是某一条路径合成的,因此底层其他字母被限制了,你的做法是独立判断的每个字母,导致底层被影响的字母没有做判断。我给了一种dp做法,是将一行整体作为判断,可以过。
已修正
想问问大佬写的f(i,j,k)是什么格式编写的 $f(i,j,k) $吗?
两个$包围的吗
对滴