756. 金字塔转换矩阵

题目

现在，我们用一些方块来堆砌一个金字塔。 每个方块用仅包含一个字母的字符串表示。
使用三元组表示金字塔的堆砌规则如下：
对于三元组 ABC ，C 为顶层方块，方块 A 、B 分别作为方块 C 下一层的的左、右子块。当且仅当 ABC 是被允许的三元组，我们才可以将其堆砌上。
初始时，给定金字塔的基层 bottom，用一个字符串表示。一个允许的三元组列表 allowed，每个三元组用一个长度为 3 的字符串表示。
如果可以由基层一直堆到塔尖就返回 true ，否则返回 false 。
示例 1：

  1. 输入：bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
  2. 输出：true
  3. 解释：
  4. 可以堆砌成这样的金字塔:
  5.     A
  6.    / \
  7.   G   E
  8.  / \ / \
  9. B   C   D
  11. 因为符合 BCG、CDE 和 GEA 三种规则。

示例 2：

输入：bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
输出：false
解释：
无法一直堆到塔尖。
注意, 允许存在像 ABC 和 ABD 这样的三元组，其中 C != D。

提示：

  • bottom 的长度范围在 [2, 8]。
  • allowed 的长度范围在[0, 200]。
  • 方块的标记字母范围为{'A', 'B', 'C', 'D', 'E', 'F', 'G'}。

题解

这个说实话不难，多写几个循环即可解决，但是这是没有技术含量的代码，由于这题是我在模拟面试上遇到的，所以就不讲究什么技巧，直接暴力求稳。

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        L = []
        n = len(bottom)
        L.append([[c] for c in bottom])
        for i in range(1, n):
            base1 = []
            for j in range(n-i):
                base2 = set()
                # print(j, L[i-1][j], L[i-1][j+1])
                for x in L[i-1][j]:
                    for y in L[i-1][j+1]:
                        # print(x+y)
                        for c in allowed:
                            if x+y == c[:2]:
                                base2.add(c[2])
                base1.append(list(base2))
            L.append(base1)
        # print(L)
        return len(L[-1][-1])!=0

官方代码

首先建立了一个映射T， T[x][y] = {set of z} 里面包含了 (x,y) 所对应的所有父块。
然后写了一个迭代器 build，通过深搜生成以 A 为基底的下一行的所有组合。
代码非常简洁优美，我已经学废了。。。

class Solution(object):
    def pyramidTransition(self, bottom, allowed):
        T = collections.defaultdict(set)
        for u, v, w in allowed:
            T[u, v].add(w)

        #Comments can be used to cache intermediate results
        #seen = set()
        def solve(A):
            if len(A) == 1: return True
            #if A in seen: return False
            #seen.add(A)
            return any(solve(cand) for cand in build(A, []))

        def build(A, ans, i = 0):
            if i + 1 == len(A):
                yield "".join(ans)
            else:
                for w in T[A[i], A[i+1]]:
                    ans.append(w)
                    for result in build(A, ans, i+1):
                        yield result
                    ans.pop()

        return solve(bottom)