难度：★★★☆☆
类型：字符串
方法：回溯算法

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

现在，我们用一些方块来堆砌一个金字塔。 每个方块用仅包含一个字母的字符串表示。

使用三元组表示金字塔的堆砌规则如下：

对于三元组(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'}。

解答

这是一个堆砖块的游戏，我们使用回溯法解决这个问题。将复杂问题分解成有限个可重复的简单问题是用计算机解决问题的主要手段，也是一个重要的能力，回溯法，动态规划，深度优先搜索等等算法都采用这个思路。

我们先来观察一下题目给出的两个变量，bottom就是用字符串表达的金字塔基座，allowed是允许的砖块堆叠关系，即相邻两个砖块上允许放哪个砖块。我们先把allowed数组做一个转化，准备一个字典pedestal_to_brick，字典的键是砖块对，值是砖块对允许支撑的砖块的列表。例如，allowed为[‘ABC’,’ABD’]时，转化为字典pedestal_to_brick就是{‘AB’: [‘C’, ‘D’]}。

回溯算法常常用递归实现。接下来我们就可以定义回溯函数build了，金字塔是一层一层堆叠的，我们把当前相邻的两层（即当前层current_layer及其所依托的底座pedestal_layer）作为函数的输入，函数的输出为布尔量，表达当前状态能否完成金字塔的构建。函数执行以下操作：

1. 特殊情况的处理，如果当前层的底座pedestal_layer只有一个砖块了，说明已经到达了金字塔的塔顶，直接返回True；如果当前层的底座pedestal_layer正好比当前层current_layer多一个砖块，说明当前层已经完成了构建，可以把当前层作为底座，通过递归调用本函数在此基础上构建新的层了；

2. 其他普通情况，首先定位一下当前层的完成进度，找到当前需要继续构建的位置，然后取出来该位置的两个底座砖块组成长度为2的字符串pedestal，如果这两个砖块pedestal在pedestal_to_brick的键列表中是存在的，那么可以遍历这两个砖块可以支撑起的所有砖块，然后递归的构建下一种状态。如果循环结束，仍然无法找到可以构建完成金字塔的情况，则返回False。

注意每当构建新层时，当前层初始化为空字符串。

from collections import defaultdict


class Solution:
    def pyramidTransition(self, bottom, allowed):
        pedestal_to_brick = defaultdict(list)
        for i, j, k in allowed:
            pedestal_to_brick[i+j].append(k)

        def build(pedestal_layer, construct_layer):
            if len(pedestal_layer) == 1:
                return True

            if len(construct_layer) + 1 == len(pedestal_layer):
                return build(construct_layer, '')

            pedestal = pedestal_layer[len(construct_layer):len(construct_layer) + 2]
            if pedestal in pedestal_to_brick:
                for brick in pedestal_to_brick[pedestal]:
                    if build(pedestal_layer, construct_layer + brick):
                        return True
            return False
        return build(bottom, '')

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析