金字塔转换矩阵

难度: Medium

你正在把积木堆成金字塔。每个块都有一个颜色，用一个字母表示。每一行的块比它下面的行 少一个块 ，并且居中。

为了使金字塔美观，只有特定的 三角形图案 是允许的。一个三角形的图案由 两个块 和叠在上面的 单个块 组成。模式是以三个字母字符串的列表形式 allowed 给出的，其中模式的前两个字符分别表示左右底部块，第三个字符表示顶部块。

例如，"ABC" 表示一个三角形图案，其中一个 “C” 块堆叠在一个 'A' 块(左)和一个 'B' 块(右)之上。请注意，这与 "BAC" 不同，"B" 在左下角，"A" 在右下角。

你从底部的一排积木 bottom 开始，作为一个单一的字符串，你必须使用作为金字塔的底部。

在给定 bottom 和 allowed 的情况下，如果你能一直构建到金字塔顶部，使金字塔中的 每个三角形图案 都是允许的，则返回 true ，否则返回 false 。

示例 1：

输入：bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
输出：true
解释：允许的三角形模式显示在右边。
从最底层(第3层)开始，我们可以在第2层构建“CE”，然后在第1层构建“E”。
金字塔中有三种三角形图案，分别是“BCC”、“CDE”和“CEA”。都是允许的。

示例 2：

输入：bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"]
输出：false
解释：允许的三角形模式显示在右边。
从最底层(游戏邦注:即第4个关卡)开始，创造第3个关卡有多种方法，但如果尝试所有可能性，你便会在创造第1个关卡前陷入困境。

提示：

2 <= bottom.length <= 6
0 <= allowed.length <= 216
allowed[i].length == 3
所有输入字符串中的字母来自集合 {'A', 'B', 'C', 'D', 'E', 'F', 'G'}。
allowed 中所有值都是 唯一的

Submission

运行时间: 48 ms

内存: 17.5 MB

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        trans = defaultdict(list)
        for p in allowed:
            trans[p[:2]].append(p[2])

        @cache
        def search(a, b):
            # a为底层，b为下一层左边的字符
            if len(b) > 1 and not search(b, ''):
                return False
            if len(a) == 2:
                if b:
                    return any(search(b + t, '') for t in trans[a])
                else:
                    return a in trans
            else:
                return any(search(a[1:], b + t) for t in trans[a[:2]])

        return search(bottom, '')

Explain

此题解使用深度优先搜索（DFS）配合记忆化来判断是否能从底层的积木字符串构建到金字塔的顶端。首先，使用哈希表 `trans` 来存储每种可能的底部积木组合和对应能放在其上的顶部积木的列表。然后，定义一个递归函数 `search(a, b)`，其中 `a` 代表当前层正在处理的积木字符串，`b` 代表下一层已经部分构建的字符串。如果 `a` 的长度为2且 `b` 非空，函数尝试将 `b` 作为新的底层来继续构建金字塔。如果 `b` 为空，函数检查 `a` 是否存在于 `trans` 中。如果 `a` 的长度大于2，递归地对 `a` 的子串和 `b` 扩展后的字符串进行搜索。整个递归过程都用 `cache` 装饰器进行记忆化，以避免重复计算。最终，从 `bottom` 字符串开始调用 `search` 函数，并判断是否可以成功构建到金字塔顶部。

时间复杂度: O(T^(N-1))，其中 T 是每个积木对可能的顶部积木选择数，N 是输入字符串 `bottom` 的长度。

空间复杂度: O(L + N + M)，其中 L 是 `allowed` 的长度，N 是 `bottom` 的长度，M 是记忆化存储的大小。

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        trans = defaultdict(list)
        for p in allowed:
            trans[p[:2]].append(p[2])  # 创建从底部积木对到顶部积木的映射

        @cache
        def search(a, b):
            # a为当前层正在处理的积木字符串，b为下一层已经部分构建的字符串
            if len(b) > 1 and not search(b, ''):
                return False
            if len(a) == 2:
                if b:
                    return any(search(b + t, '') for t in trans[a])  # 尝试所有顶部积木以继续构建
                else:
                    return a in trans
            else:
                return any(search(a[1:], b + t) for t in trans[a[:2]])  # 移动到下一个积木对

        return search(bottom, '')  # 从底部字符串开始构建金字塔

Explore

在`search`函数中，`b`代表下一层已经部分构建的字符串。当`b`的长度大于1时，意味着我们已经为整个下一层构建了足够的字符，现在需要检查这一层是否能作为新的底层继续向上构建金字塔。通过调用`search(b, '')`，我们尝试将`b`看作新的底层字符串，并尝试从这一层继续构建金字塔顶部。如果这一操作返回`False`，则说明从`b`开始不能成功构建到金字塔顶端，当前的构建方案失败，需要回溯尝试其他可能性。

当`len(a) == 2`且`b`为空时，意味着`a`是当前层唯一的剩余积木对，我们需要检查是否存在任何顶部积木可以放在`a`两个积木之上。直接返回`a in trans`是为了确认是否有任何有效的顶部积木映射存在于`trans`中。如果存在，表示存在至少一个顶部积木可以支持构建下一层，因此这一检查是确定是否有可能从`a`继续构建的关键步骤。

这种递归策略的优势在于它能一步步构建下一层的可能性，同时逐渐缩减当前层的处理范围。在每次递归中，通过取`a`的前两个字符并查询可能的顶部积木`t`，然后将这些`t`添加到下一层字符串`b`中，这样逐步构建下一层的同时，减少当前层的长度（通过`a[1:]`）。这种方法允许算法在每一步都尝试所有可能的顶部积木配置，以此来寻找能成功构建整个金字塔的路径。

`defaultdict(list)`允许我们在字典中自动初始化不存在的键对应的值为一个空列表。在构建`trans`字典时，我们遍历`allowed`列表中的每个字符串，取其前两个字符作为键，而第三个字符作为该键对应的列表中的一个元素。这样，对于每个底部积木对，我们可以很方便地查找所有可能放在其上的顶部积木。使用`defaultdict(list)`的好处在于简化了字典初始化和添加元素的代码，使得添加新映射非常简洁且高效。