南昌城乡住房建设厅网站,网站全程设计技术,天津建设工程注册中心网站,wordpress找回密码文章目录1. 题目2. 解题1. 题目
现在#xff0c;我们用一些方块来堆砌一个金字塔。 每个方块用仅包含一个字母的字符串表示。
使用三元组表示金字塔的堆砌规则如下#xff1a;
对于三元组(A, B, C) #xff0c;“C”为顶层方块#xff0c;方块“A”、“B”分别作为方块“…
文章目录1. 题目2. 解题1. 题目
现在我们用一些方块来堆砌一个金字塔。 每个方块用仅包含一个字母的字符串表示。
使用三元组表示金字塔的堆砌规则如下
对于三元组(A, B, C) “C”为顶层方块方块“A”、“B”分别作为方块“C”下一层的左、右子块。当且仅当(A, B, C)是被允许的三元组我们才可以将其堆砌上。
初始时给定金字塔的基层 bottom用一个字符串表示。 一个允许的三元组列表 allowed每个三元组用一个长度为 3 的字符串表示。
如果可以由基层一直堆到塔尖就返回 true 否则返回 false 。
示例 1
输入bottom BCD, allowed [BCG, CDE, GEA, FFF]
输出true
解析
可以堆砌成这样的金字塔:A/ \G E/ \ / \
B C D因为符合(B, C, G), (C, D, E) 和 (G, E, A) 三种规则。示例 2
输入bottom AABA, allowed [AAA, AAB, ABA, ABB, BAC]
输出false
解析
无法一直堆到塔尖。
注意, 允许存在像 (A, B, C) 和 (A, B, D) 这样的三元组其中 C ! D。提示
bottom 的长度范围在 [2, 8]。
allowed 的长度范围在[0, 200]。
方块的标记字母范围为{A, B, C, D, E, F, G}。来源力扣LeetCode 链接https://leetcode-cn.com/problems/pyramid-transition-matrix 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
暴力回溯穷举即可
class Solution {bool ans false;vectorchar ch {A, B, C, D, E, F, G};
public:bool pyramidTransition(string bottom, vectorstring allowed) {int n bottom.size();unordered_setstring s(allowed.begin(), allowed.end());vectorvectorchar gold(n, vectorchar(n, *));for(int j 0; j n; j) {gold[n-1][j] bottom[j];//填充最底层的字母}dfs(gold, s, n-2, 0);//从倒数第二行第0列开始搜索return ans;}void dfs(vectorvectorchar gold, unordered_setstring s, int i, int j){if(ans true)return;char origin gold[i][j];//记录原始字母for(int k 0; k 7; k)//填入7种可能的字母{string t string(1, gold[i1][j])gold[i1][j1]char(Ak);// 三元组字符串if(s.find(t) ! s.end())//字符串在字典中{if(i j)//这一行填完了{if(i 0)ans true;gold[i][j] char(Ak);//填入可能的字母dfs(gold, s, i-1, 0);//下一行0列gold[i][j] origin;//恢复现场}else{gold[i][j] char(Ak);dfs(gold, s, i, j1);//当前行下一列gold[i][j] origin;}}}}
};8 ms 9.2 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
