main.cpp

// Source: https://leetcode.com/problems/pyramid-transition-matrix
// Title: Pyramid Transition Matrix
// Difficulty: Medium
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// You are stacking blocks to form a pyramid. Each block has a color, which is represented by a single letter. Each row of blocks contains **one less block** than the row beneath it and is centered on top.
//
// To make the pyramid aesthetically pleasing, there are only specific **triangular patterns** that are allowed. A triangular pattern consists of a **single block** stacked on top of **two blocks**. The patterns are givenas a list ofthree-letter strings `allowed`, where the first two characters of a pattern represent the left and right bottom blocks respectively, and the third character is the top block.
//
// - For example, `"ABC"` represents a triangular pattern with a `'C'` block stacked on top of an `'A'` (left) and `'B'` (right) block. Note that this is different from `"BAC"` where `'B'` is on the left bottom and `'A'` is on the right bottom.
//
// You start with a bottom row of blocks `bottom`, given as a single string, that you **must** use as the base of the pyramid.
//
// Given `bottom` and `allowed`, return `true` if you can build the pyramid all the way to the top such that **every triangular pattern** in the pyramid is in `allowed`, or `false` otherwise.
//
// **Example 1:**
// https://assets.leetcode.com/uploads/2021/08/26/pyramid1-grid.jpg
//
// ```
// Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
// Output: true
// Explanation: The allowed triangular patterns are shown on the right.
// Starting from the bottom (level 3), we can build "CE" on level 2 and then build "A" on level 1.
// There are three triangular patterns in the pyramid, which are "BCC", "CDE", and "CEA". All are allowed.
// ```
//
// **Example 2:**
// https://assets.leetcode.com/uploads/2021/08/26/pyramid2-grid.jpg
//
// ```
// Input: bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"]
// Output: false
// Explanation: The allowed triangular patterns are shown on the right.
// Starting from the bottom (level 4), there are multiple ways to build level 3, but trying all the possibilites, you will get always stuck before building level 1.
// ```
//
// **Constraints:**
//
// - `2 <= bottom.length <= 6`
// - `0 <= allowed.length <= 216`
// - `allowed[i].length == 3`
// - The letters in all input strings are from the set `{'A', 'B', 'C', 'D', 'E', 'F'}`.
// - All the values of `allowed` are **unique**.
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

// DFS
//
// We do DFS by column, since above block is effect directly by below ones.
class Solution {
  unordered_map<string, vector<char>> allowMap;

 public:
  bool pyramidTransition(string bottom, vector<string>& allowed) {
    for (auto pattern : allowed) {
      allowMap[pattern.substr(0, 2)].push_back(pattern[2]);
    }

    return dfs({bottom[0]}, {bottom[1]}, bottom);
  }

  bool dfs(string left, string right, string bottom) {
    int n = bottom.size(), l = left.size(), r = right.size();
    if (r == n) return true;
    if (r == l + 1) return dfs(right, {bottom[r]}, bottom);

    auto candidate = allowMap.find({left[r - 1], right[r - 1]});
    if (candidate == allowMap.cend()) return false;
    for (auto ch : candidate->second) {
      if (dfs(left, right + ch, bottom)) return true;
    }
    return false;
  }
};

// DFS + DP
//
// We do DFS by column, since above block is effect directly by below ones.
class Solution2 {
  unordered_map<string, vector<char>> allowMap;
  unordered_map<string, bool> mem;  // left+"-"+right

 public:
  bool pyramidTransition(string bottom, vector<string>& allowed) {
    for (auto pattern : allowed) {
      allowMap[pattern.substr(0, 2)].push_back(pattern[2]);
    }

    return dfs({bottom[0]}, {bottom[1]}, bottom);
  }

  bool dfs(string left, string right, string bottom) {
    int n = bottom.size(), l = left.size(), r = right.size();
    if (r == n) return true;
    if (r == l + 1) return dfs(right, {bottom[r]}, bottom);

    auto hashKey = left + "-" + right;
    if (mem.contains(hashKey)) return mem[hashKey];

    auto candidate = allowMap.find({left[r - 1], right[r - 1]});
    if (candidate == allowMap.cend()) {
      mem[hashKey] = false;
      return false;
    }

    for (auto ch : candidate->second) {
      if (dfs(left, right + ch, bottom)) {
        mem[hashKey] = true;
        return true;
      }
    }

    mem[hashKey] = false;
    return false;
  }
};