金字塔转换矩阵

作者 
class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        string groups[6][6];
        for (auto& s : allowed)
        {
            groups[s[0] - 'A'][s[1] - 'A'] += s[2];
        }
​
        int n = bottom.size();
        vector<string> pyramid(n);
        pyramid[n - 1] = move(bottom);
​
        unordered_set<string> memo;
​
        auto dfs = [&](this auto&& dfs, int i, int j) -> bool
        {
            if (i < 0) return true;
​
            if (memo.contains(pyramid[i])) return false;
​
            if (j == i + 1)
            {
                return dfs(i - 1 , 0);
            }
​
            for (char& c : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A'])
            {
                pyramid[i] += c;
                if (dfs(i, j + 1)) return true;
                pyramid[i].pop_back();
            }
        };
​
        return dfs(n - 2, 0);
    }
};

第一步：数据结构的预处理（优化查找）

思考：

我们在堆金字塔时，核心操作是：“给定底层的两个积木（左L，右R），上面能放什么积木（Top）？”

如果直接遍历输入的 allowed 列表（例如 [“ABC”, “ABD”, …]），每次查询都需要 O(N) 的时间，这在递归中太慢了。

推导：

我们需要一个 O(1) 的查询方式。

  • 因为积木只有 ‘A’ 到 ‘F’（一共6种），我们可以用一个二维数组或者哈希表来存储映射关系。
  • groups[Left][Right] = “可以放在上面的所有积木字符”。

代码对应：

string groups[6][6];
for (auto& s : allowed) {
    // s[0]是左，s[1]是右，s[2]是顶
    groups[s[0] - 'A'][s[1] - 'A'] += s[2];
}

第二步：定义状态与构建金字塔结构

思考：

我们需要一层一层往上堆。

  • 输入是 bottom（最底层），假设它是第 n-1 层。
  • 我们要构建第 n-2 层，直到第 0 层（塔尖，只有1个积木）。
  • 如果在构建过程中发现某一层无论如何都无法构建出下一层，就需要回溯。

推导：

我们需要一个数据结构来保存当前正在构建的金字塔。

  • vector<string> pyramid(n)：pyramid[i] 代表第 i 层的字符串。
  • 初始化时，把 bottom 放入最底层。

代码对应：

int n = bottom.size();
vector<string> pyramid(n);
pyramid[n - 1] = move(bottom); // 初始化底层

第三步：设计 DFS 递归逻辑（核心算法）

思考：

如何填满这个金字塔？我们可以定义一个递归函数 dfs(i, j)。

  • i：当前正在构建的层数（从 n-2 往上到 0）。
  • j：当前层正在填写的第几个字符。

逻辑流：

  1. 成功终止条件：如果 i < 0，说明第0层（塔尖）都填好了，成功！返回 true。
  2. 层级切换：如果 j == i + 1，说明当前第 i 层已经填满了（第 i 层长度应为 i+1）。那么就开始构建上一层：dfs(i - 1, 0)。
  3. 尝试填空：
    • 当前要填的位置是 pyramid[i][j]。
    • 它的“地基”是下一层的两个积木：左边 pyramid[i+1][j]，右边 pyramid[i+1][j+1]。
    • 查表 groups，看看能放什么字符。
  4. 回溯：
    • 遍历所有可能的字符，填入 pyramid[i]。
    • 递归调用 dfs(i, j + 1) 继续填当前层的下一个位置。
    • 如果递归返回 true，直接返回 true。
    • 如果不行，把刚才填的字符拿掉（pop_back），试下一个。

代码对应：

auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
    if (i < 0) return true; // 塔尖完成
​
    // ... (记忆化部分先跳过)
​
    // 当前层填完，去填上一层
    if (j == i + 1) {
        return dfs(i - 1, 0);
    }
​
    // 查找下一层(i+1)的两个支撑点能生成什么
    char left = pyramid[i + 1][j];
    char right = pyramid[i + 1][j + 1];
    
    for (char& c : groups[left - 'A'][right - 'A']) {
        pyramid[i] += c;       // 尝试放置积木 c
        if (dfs(i, j + 1)) return true; // 继续递归
        pyramid[i].pop_back(); // 回溯：撤销选择
    }
    return false; // 所有可能都试过了，不行
};

第四步：优化剪枝（记忆化 Memoization）

思考：

在递归过程中，我们会多次遇到相同的情况。

比如，第 i+1 层是 “ABC” 时，我们在尝试构建第 i 层。如果我们之前已经证明过以 “ABC” 为底座无法构建出塔尖，那么下次再遇到 “ABC” 作为底座时，就不用再浪费时间去试了。

推导：

  • 使用一个 unordered_set<string> memo。
  • 存储那些已经被证明是死胡同的层。
  • 注意：你提供的代码片段中逻辑稍微有点跳跃（且缺少了插入操作），标准的逻辑应该是：
    1. 当我们要基于 pyramid[i+1] 构建第 i 层时（或者构建完第 i 层准备去构建 i-1 层时）。
    2. 如果发现 pyramid 的当前状态以前失败过，直接返回 false。
    3. 如果尝试了所有可能性都失败了，在返回 false 之前，把当前这个导致失败的字符串加入 memo。

你代码中的逻辑分析：

if (memo.contains(pyramid[i])) return false;

这一行其实是用来检查当前正在构建的这一行是否曾经被标记为“无法成功向上堆叠”。

  • 注意：这里的逻辑在标准解法中通常是检查 pyramid[i+1]（即底座），或者在 j == i + 1 换层的时候检查。
  • 缺失的关键行：在你提供的代码片段中，缺少了 memo.insert(...)。通常在函数末尾返回 false 之前，需要加上 memo.insert(pyramid[i]);（或者插入底座），否则 memo.contains 永远查不到东西。

总结推导路径

  1. 输入太难查 \rightarrow 建立 groups[6][6] 邻接表。
  2. 不知道塔长什么样 \rightarrow 建立 pyramid 字符串数组模拟物理结构。
  3. 怎么盖楼 \rightarrow dfs(i, j)，利用下一层的 [j] 和 [j+1] 决定当前层的 [j]。
  4. 撞了南墙要回头 \rightarrow 回溯法（+= c 然后 pop_back）。
  5. 同样的坑不踩两次 \rightarrow memo 记录失败的字符串（这是很多 C++ Hard 题的关键优化点）。

发表评论