<p>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 <strong>one less block</strong> than the row beneath it and is centered on top.</p>

<p>To make the pyramid aesthetically pleasing, there are only specific <strong>triangular patterns</strong> that are allowed. A triangular pattern consists of a <strong>single block</strong> stacked on top of <strong>two blocks</strong>. The patterns are given&nbsp;as a list of&nbsp;three-letter strings <code>allowed</code>, where the first two characters of a pattern represent the left and right bottom blocks respectively, and the third character is the top block.</p>

<ul>
	<li>For example, <code>&quot;ABC&quot;</code> represents a triangular pattern with a <code>&#39;C&#39;</code> block stacked on top of an <code>&#39;A&#39;</code> (left) and <code>&#39;B&#39;</code> (right) block. Note that this is different from <code>&quot;BAC&quot;</code> where <code>&#39;B&#39;</code> is on the left bottom and <code>&#39;A&#39;</code> is on the right bottom.</li>
</ul>

<p>You start with a bottom row of blocks <code>bottom</code>, given as a single string, that you <strong>must</strong> use as the base of the pyramid.</p>

<p>Given <code>bottom</code> and <code>allowed</code>, return <code>true</code><em> if you can build the pyramid all the way to the top such that <strong>every triangular pattern</strong> in the pyramid is in </em><code>allowed</code><em>, or </em><code>false</code><em> otherwise</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/26/pyramid1-grid.jpg" style="width: 600px; height: 232px;" />
<pre>
<strong>Input:</strong> bottom = &quot;BCD&quot;, allowed = [&quot;BCC&quot;,&quot;CDE&quot;,&quot;CEA&quot;,&quot;FFF&quot;]
<strong>Output:</strong> true
<strong>Explanation:</strong> The allowed triangular patterns are shown on the right.
Starting from the bottom (level 3), we can build &quot;CE&quot; on level 2 and then build &quot;A&quot; on level 1.
There are three triangular patterns in the pyramid, which are &quot;BCC&quot;, &quot;CDE&quot;, and &quot;CEA&quot;. All are allowed.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/26/pyramid2-grid.jpg" style="width: 600px; height: 359px;" />
<pre>
<strong>Input:</strong> bottom = &quot;AAAA&quot;, allowed = [&quot;AAB&quot;,&quot;AAC&quot;,&quot;BCD&quot;,&quot;BBE&quot;,&quot;DEF&quot;]
<strong>Output:</strong> false
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= bottom.length &lt;= 6</code></li>
	<li><code>0 &lt;= allowed.length &lt;= 216</code></li>
	<li><code>allowed[i].length == 3</code></li>
	<li>The letters in all input strings are from the set <code>{&#39;A&#39;, &#39;B&#39;, &#39;C&#39;, &#39;D&#39;, &#39;E&#39;, &#39;F&#39;}</code>.</li>
	<li>All the values of <code>allowed</code> are <strong>unique</strong>.</li>
</ul>

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

using namespace std;

class Solution {
public:
    // Preprocess allowed triples into a map where key is a pair of characters and value is a list of possible tops
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        // Map to store allowed pairs and possible top blocks
        unordered_map<string, vector<char>> allowed_map;
        
        // Build the map from allowed triples
        for (const string& rule : allowed) {
            string base = rule.substr(0, 2); // The first two characters are the base
            allowed_map[base].push_back(rule[2]); // The third character is the top block
        }

        // Memoization map to cache subproblems
        unordered_map<string, bool> memo;
        
        // Start the backtracking process
        return dfs(bottom, allowed_map, memo);
    }

private:
    // DFS with pruning and memoization
    bool dfs(const string& bottom, unordered_map<string, vector<char>>& allowed_map, unordered_map<string, bool>& memo) {
        // If we've reduced the pyramid to one block, return true
        if (bottom.size() == 1) {
            return true;
        }

        // Check if this subproblem has already been solved
        if (memo.find(bottom) != memo.end()) {
            return memo[bottom];
        }

        // Try to build the next row
        vector<string> next_rows = generateNextRow(bottom, allowed_map);

        // Try all possible next rows
        for (const string& next_row : next_rows) {
            if (dfs(next_row, allowed_map, memo)) {
                memo[bottom] = true;
                return true;
            }
        }

        memo[bottom] = false; // Memoize this result
        return false;
    }

    // Generate all possible next rows from the current row
    vector<string> generateNextRow(const string& bottom, unordered_map<string, vector<char>>& allowed_map) {
        vector<string> results;
        string current_row = "";

        // Use a helper function to recursively generate all combinations of the next row
        generateCombinations(bottom, allowed_map, current_row, 0, results);
        return results;
    }

    // Recursive function to generate all combinations of the next row
    void generateCombinations(const string& bottom, unordered_map<string, vector<char>>& allowed_map, string& current_row, int index, vector<string>& results) {
        if (index == bottom.size() - 1) {
            results.push_back(current_row);
            return;
        }

        // Get the pair of adjacent blocks
        string base = bottom.substr(index, 2);

        // If no valid top block exists for this pair, stop
        if (allowed_map.find(base) == allowed_map.end()) {
            return;
        }

        // Try all possible top blocks for this pair
        for (char top : allowed_map[base]) {
            current_row.push_back(top);
            generateCombinations(bottom, allowed_map, current_row, index + 1, results);
            current_row.pop_back(); // Backtrack
        }
    }
};

84700