<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>

class Solution {
private:
    // Function to generate all possible strings for the next level
    void Possible_Strings(int ind, string &top, unordered_map<string, vector<char>>& adj,
                          vector<string>& top_strings, string cur_string) {
        // Base case: if we have built a full string for the next level
        if (ind == top.size()) {
            top_strings.push_back(cur_string);
            return;
        }
        
        // Get the two characters from the current level
        string node = top.substr(ind - 1, 2);
        
        // Try all possible transitions for the current "node"
        if (adj.find(node) != adj.end()) {
            for (char adjnode : adj[node]) {
                cur_string.push_back(adjnode); // Add the adjacent node
                Possible_Strings(ind + 1, top, adj, top_strings, cur_string); // Recurse
                cur_string.pop_back();         // Backtrack
            }
        }
    }

    // DFS helper function with memoization
    bool dfs(string bottom, unordered_map<string, vector<char>>& adj, unordered_map<string, bool>& memo) {
        // If we already solved this subproblem, return the stored result
        if (memo.find(bottom) != memo.end()) {
            return memo[bottom];
        }
        
        // Base case: if the bottom has only one character, we can build the pyramid
        if (bottom.size() == 1) {
            return true;
        }
        
        // Generate all possible top strings for the next level
        vector<string> top_strings;
        Possible_Strings(1, bottom, adj, top_strings, "");
        
        // Recursively check all possible next levels
        for (string top : top_strings) {
            if (dfs(top, adj, memo)) { // If we can build the pyramid from this top level
                memo[bottom] = true;   // Memoize the result for this bottom string
                return true;
            }
        }
        
        // If none of the possible top levels work, memoize and return false
        memo[bottom] = false;
        return false;
    }

public:
    // Main function to solve the pyramid transition problem
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        // Build the adjacency list from the allowed transitions
        unordered_map<string, vector<char>> adj;
        for (const string& rule : allowed) {
            string node = rule.substr(0, 2);  // First two characters as the node
            char adjnode = rule[2];           // Third character is the possible transition
            adj[node].push_back(adjnode);
        }
        
        // Memoization table to store results for different bottom strings
        unordered_map<string, bool> memo;
        
        // Start the DFS process from the bottom level with memoization
        return dfs(bottom, adj, memo);
    }
};

86800