Java 中的金字塔过渡矩阵

在此问题中，我们的任务是逐块构建金字塔。每个块都有一个与字母对应的颜色。金字塔的构建方式是，每一层比其下方的一层少一个块。要构建金字塔，一个块堆叠在它正下方的两个相邻块的上方，形成一个三角形。

堆叠积木时，我们需要遵守特定的规则：只允许使用特定的三角形设计。使用一个三字母的 字符串 来表示模式，前两个字母表示底部积木的左右颜色，第三个字母表示堆叠在上面的积木的颜色。

我们还得到一份允许的设计列表，以及金字塔的底部，形式为一个字符串 bottom。目标是找出是否可以完全构建到顶部，同时确保形成的每个三角形模式都包含在允许的模式列表中。如果可以这样构建，则返回 true；否则，返回 false。

示例 1

输入

String bottom = "BCD"

String allow = ["BCC", "CDE", "CEA", "FFF"]

输出： true

解释

右侧显示了允许的三角形模式。

通过在第 2 层构建“CE”，然后在第 1 层构建“A”，我们可以从底部（第 3 层）开始。

“BCC”、“CDE”和“CEA”是构成金字塔的三个三角形设计。它们都已获批准。

示例 2

输入

String bottom = "AAAA"

String allowed = ["AAB", "AAC", "BCD", "BBE", "DEF"]

输出： false

解释

右侧显示了允许的三角形模式。

从第 4 层开始，我们可以通过多种方式构建第 3 层，但如果我们尝试所有选项，最终都会被困住，无法构建第 1 层。

方法：使用递归深度优先搜索

使用深度优先搜索，递归函数 dfs 从底部开始，逐层构建潜在的金字塔配置。根据当前正在分析的积木，每个 dfs 调用都尝试构建下一层。

在给定的代码中，为了确定是否可以从给定的底部 (bottom) 和允许的过渡 (allow) 构建金字塔，一个 Java 程序使用位运算和带记忆化（memoization）的深度优先搜索 (DFS) 来创建一个金字塔过渡矩阵。位表示用于在过渡矩阵 (trans_Matrix) 中存储有效的过渡。DFS 函数会迭代地构建金字塔，验证每一层是否都可以根据提供的规则创建。通过记忆化（memorization hash map）来优化重复的状态计算，从而提高效率。基本情况保证了当顶部只剩下一块积木时，函数返回 true。

算法

步骤 1： 为了使用位表示来存储潜在的过渡，创建一个名为 trans_Matrix[7][7] 的二维整型数组。

步骤 2： 使用记忆化 HashMap 来保存先前计算的结果以进行优化。

步骤 3： 逐一遍历 allow 列表中的每个过渡字符串。

步骤 3.1： 将过渡的第一个和第二个字符分别提取为 first 和 second。

步骤 3.2： 获取它们的 ASCII 值并减去 'A'，将它们转换为索引。

步骤 3.3： 使用按位或（bitwise OR）设置 trans_Matrix 中匹配的条目，以存储到第三个字符的过渡。

步骤 4： 使用一个空的 StringBuilder 作为 nextLevel，并将 bottom 作为 curr_Level 来调用 dfs(curr_Level, nextLevel) 方法。

步骤 5： 如果 curr_Level 只有一个块（金字塔已正确创建），则返回 true。

步骤 6： 如果 nextLevel 达到了所需的长度 (curr_Level.length() - 1)，

步骤 6.1： 对于下一层，递归调用 dfs(nextLevel.toString(), new StringBuilder())。

步骤 7： 使用 curr_Level + "." + nextLevel.toString() 创建一个唯一的键。

步骤 8： 如果该键存在于记忆化中，则返回其存储的值。

步骤 9： 使用 curr_Level，查找第一个和第二个积木的索引。

步骤 10： 从 trans_Matrix 中检索 potentialTransitions.[first] [second]。

步骤 11： 循环遍历七个不同的字符（'A' 到 'G'）。

步骤 11.1： 如果字符 'A' + i 的过渡是可行的，将其添加到 nextLevel。

步骤 11.1.1： 递归调用 dfs(curr_Level, nextLevel)。

步骤 11.1.2： 如果成功，则将 true 存储在记忆化中并返回 true。

步骤 11.1.3： 如果不成功，则回溯并删除最后添加的字符。

步骤 12： 如果没有合适的过渡，则返回 false 并将 false 存储在记忆化中。

步骤 13： 将 allow 列表和 bottom 字符串设置为初始值。

步骤 14： 创建类的一个实例后，调用 pyramidTransition(bottom, allow)。

步骤 15： 返回结果（false 或 true）。

实施

输出

 
true   

复杂度分析

上述代码的时间复杂度为 O(7^(N-1))，其中 'N' 表示 bottom 的长度，空间复杂度为 O(7^(N-1))，因为每个递归步骤在每个过渡处都可以分支出七个选择。