0756. Pyramid Transition Matrix ======================================================================================================================== 题目信息 -------- :题号: 0756 :难度: Medium :主题: 字符串、组合构造、状态搜索 :原题: `LeetCode 0756 `_ :重点: 每个三字符规则按“左下、右下、上方”解释且左右顺序不能交换;需要判断是否存在至少一种方式从指定底层构造到单个顶块 题目重述 -------- 使用字母表示不同颜色的方块。金字塔最底层由字符串 ``bottom`` 给出;其上每一层都比下一层少一个方块,并且每个上层方块正好位于下层一对相邻方块之上。 数组 ``allowed`` 中的每个三字符字符串表示一种允许的局部结构:前两个字符分别是左下方块和右下方块,第三个字符是可以放在它们上方的方块。左右位置有区别,例如规则 ``"ABC"`` 不能当作 ``"BAC"`` 使用。 请判断是否存在一种选择,使金字塔中的每个局部三角结构都属于 ``allowed``,并最终构造出只含一个方块的顶层。 ``bottom`` 的长度在 ``[2, 6]`` 范围内,``allowed`` 的长度在 ``[0, 216]`` 范围内;所有字符串只包含 ``A`` 至 ``F``,每条规则长度均为 3,且规则互不重复。 自建示例 -------- 从四块底层连续构造三层: .. code-block:: text 输入:bottom = "ABCD", allowed = ["ABE","BCF","CDA","EFB","FAC"] 输出:true 解释:底层的相邻对 AB、BC、CD 分别生成 E、F、A,得到第二层 "EFA";相邻对 EF、FA 再生成 B、C,得到第三层 "BC";规则 "BCF" 最终生成顶块 F,因此存在完整构造路径。 左右顺序不能互换: .. code-block:: text 输入:bottom = "BA", allowed = ["ABC","CAA"] 输出:false 解释:底层相邻对是 "BA",而规则只允许 "AB" 上方放置 C;规则的前两个字符有左右顺序,因此无法生成上一层。