0756. Pyramid Transition Matrix

题目信息

题号:

0756

难度:

Medium

主题:

字符串、组合构造、状态搜索

原题:

LeetCode 0756

重点:

每个三字符规则按“左下、右下、上方”解释且左右顺序不能交换;需要判断是否存在至少一种方式从指定底层构造到单个顶块

题目重述

使用字母表示不同颜色的方块。金字塔最底层由字符串 bottom 给出;其上每一层都比下一层少一个方块,并且每个上层方块正好位于下层一对相邻方块之上。

数组 allowed 中的每个三字符字符串表示一种允许的局部结构:前两个字符分别是左下方块和右下方块,第三个字符是可以放在它们上方的方块。左右位置有区别,例如规则 "ABC" 不能当作 "BAC" 使用。

请判断是否存在一种选择,使金字塔中的每个局部三角结构都属于 allowed,并最终构造出只含一个方块的顶层。

bottom 的长度在 [2, 6] 范围内,allowed 的长度在 [0, 216] 范围内;所有字符串只包含 A 至 F,每条规则长度均为 3,且规则互不重复。

自建示例

从四块底层连续构造三层:

输入:bottom = "ABCD", allowed = ["ABE","BCF","CDA","EFB","FAC"]
输出:true
解释:底层的相邻对 AB、BC、CD 分别生成 E、F、A,得到第二层 "EFA";相邻对 EF、FA 再生成 B、C,得到第三层 "BC";规则 "BCF" 最终生成顶块 F,因此存在完整构造路径。

左右顺序不能互换:

输入:bottom = "BA", allowed = ["ABC","CAA"]
输出:false
解释:底层相邻对是 "BA",而规则只允许 "AB" 上方放置 C;规则的前两个字符有左右顺序,因此无法生成上一层。