LeetCode 756. Pyramid Transition Matrix

关注
发布于: 2020 年 06 月 13 日
问题描述﻿
我们将砖块堆成一个金字塔。每块砖有一种颜色，用一个字母表示。
﻿
只有当 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 种组合，使用穷举的方式来判断。
﻿
单看文字可能不太容易理解。一图胜千言，请看下图。
﻿
﻿
简单解释一下：
在最后一层中的砖块为 ABCD。假设 AB 可能的结果为 [C,D]，BC 可能的结果为 [E,F]，CD 可能的结果为 [A]。
在倒数第二层，依次计算两个相邻砖块的可能取值。当 [C,D] 与 [E,F] 两两组合后，根据 allowed 数组 ，假设可能的结果为 [A,D]; 同样 [E,F]  分别于 [A]  进行组合，可能的结果为 [B,D]。
...，以此类推，看是否能一直到顶。
﻿
通过这个例子，我们会很自然的想到记录下 allowed 中前两个字符与第三个字符所有的对应情况，以便于后续查询。
﻿
但如何得到每一层的所有组合情况呢？我们可以这样考虑。
﻿
拿最后一层举例，看看计算倒数第二层的组合情况。
﻿
当处理 AB 时，对应的结果有 [C,D]。这时候，我们需要逐个遍历 [C,D] 中的元素，把它作为倒数第二层的第一块砖。
接着，处理 BC，它的结果对应 [E,F]。同样，遍历数组中的每个元素，将其作为第二块砖。
最后，处理 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;
};
﻿