LeetCode 756. Pyramid Transition

image.png

问题描述

我们将砖块堆成一个金字塔。每块砖有一种颜色，用一个字母表示。

只有当 ABC 是允许的三角形时，我们可以把任意颜色的 C 放到 AB 上。

我们将字符串 bottom 作为底部砖块开始，allowed 数组表示允许创建的三角形，每个元素是长度为 3 的字符串。

如果我们可以构建到金字塔的顶部，则返回 true，否则返回 false。

栗 1：

输入：bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
输出：true

解释：

可以构建如下金字塔：
    A
   / \
  G   E
 / \ / \
B   C   D

栗 2：

输入：bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
输出：false

解释：
无法构建完成。因为 BA 上只能放 C，而没有满足 "XCX" 的三角形。

注意：

• bottom 是一个字符串，长度范围在 [2, 8]。
• allowed 长度范围在 [0, 200]。
• 字符串中每个字母的取值都在 {'A', 'B', 'C', 'D', 'E', 'F', 'G'} 中。

想看英文原文的戳这里。

解题思路

思路倒是不难，但是代码实现对我来说却有些困难。但看过代码之后又觉得很简单，看易行难。

由于是金字塔形状，每层砖块的数量是以一逐渐递减的。若能堆成，则最顶部只有一个砖块。

上一层的砖块取值基于下一层来计算。因为可允许的三角形可能有多个，对于每两个相邻的砖块来说，可堆在它上面的砖块也会有多种选择。这样的话，我们需要遍历每层多种组合的情况，再一层层往上依次判断，只要有一种情况可堆到顶部，就视为可行。

所以呢，得遍历每层的 N 种组合，使用穷举的方式来判断。

单看文字可能不太容易理解。一图胜千言，请看下图。

image.png

简单解释一下：

• 在最后一层中的砖块为 ABCD。假设 AB 可能的结果为 [C,D]，BC 可能的结果为 [E,F]，CD 可能的结果为 [A]。
• 在倒数第二层，依次计算两个相邻砖块的可能取值。当 [C,D] 与 [E,F] 两两组合后，根据 allowed 数组 ，假设可能的结果为 [A,D]; 同样 [E,F] 分别于 [A] 进行组合，可能的结果为 [B,D]。
• ...，以此类推，看是否能一直到顶。

通过这个例子，我们会很自然的想到记录下 allowed 中前两个字符与第三个字符所有的对应情况，以便于后续查询。

但如何得到每一层的所有组合情况呢？我们可以这样考虑。

拿最后一层举例，看看计算倒数第二层的组合情况。

1. 当处理 AB 时，对应的结果有 [C,D]。这时候，我们需要逐个遍历 [C,D] 中的元素，把它作为倒数第二层的第一块砖。
2. 接着，处理 BC，它的结果对应 [E,F]。同样，遍历数组中的每个元素，将其作为第二块砖。
3. 最后，处理 CD， 它的结果对应 [A]，同样进行遍历，将其作为第三块砖。

这样，倒数第二层中所有可能的组合就可计算出了，每种组合包含三个砖块。

倒数第三层类似，不再赘述。

那么最终可行的判定条件是什么？很简单，当某层的砖块数量为 1 时，即喜登金顶。

由于我们是从下往上一层一层的计算，需要考虑到什么时候会换层。即当遍历到底部的最后一块砖时，便切换到下一层。

具体实现可以重点看下 dfs 函数，比文字描述更加清晰。

代码如下：

var pyramidTransition = function (bottom, allowed) {
  // 记录前两个字符与第三个字符的对应情况。{"AB":['x','x']}
  let allowMap = new Map();
  allowed.forEach((element) => {
    // 取前 2 位
    const prefix = element.slice(0, 2);
    const value = element[2];

    let list;
    if (allowMap.has(prefix)) {
      list = allowMap.get(prefix);
    } else {
      list = new Array();
    }

    list.push(value);
    allowMap.set(prefix, list);
  });

  // 递归
  return dfs(bottom, 0, "", allowMap);
};

// 递归计算
var dfs = function (bottom, i, str, map) {
   // 满足条件
  if (bottom.length === 1) {
    return true;
  }

  // 当前层的最后一个，需换到下一层
  if (i === bottom.length - 1) {
    return dfs(str, 0, "", map);
  }

  // 取前两块
  const prefix = bottom.slice(i, i + 2);
  if (map.has(prefix)) {
    const list = map.get(prefix);

    let j = 0;
    
    // 遍历每种可能的值
    while (j < list.length) {
      const b = list[j];

      // 找下一个块
      if (dfs(bottom, i + 1, str + b, map)) {
        return true;
      }

      j += 1;
    }
  }

  return false;
};