<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:
	const char MIN_LETTER = 'A';
	const char MAX_LETTER = 'F';

    auto get_mask(string_view pattern) -> unsigned int
    {
        unsigned int mask = 0;

        for (const char c : pattern)
        {
            mask *= (MAX_LETTER - MIN_LETTER + 1);
            mask += (c - MIN_LETTER);
        }

        return mask;
    }

    auto find_allowed_patterns_masks(span<const string> allowed) -> vector<bool>
    {
        const size_t possible_letters = MAX_LETTER - MIN_LETTER + 1;
        const size_t pattern_length = allowed.front().size();
        const size_t total_possible_masks = pow(possible_letters, pattern_length);

        vector<bool> allowed_patterns_masks(total_possible_masks);

        for (string_view pattern : allowed)
        {
            allowed_patterns_masks[get_mask(pattern)] = true;
        }

        return allowed_patterns_masks;
    }

	auto can_solve(const string& previous_level, string& current_level, const vector<bool>& allowed, unordered_map<string, bool>& memo) -> bool
	{
		const bool current_level_is_complete = current_level.length() == previous_level.size() - 1;

		if (current_level_is_complete)
		{
			return can_solve(current_level, memo, allowed);
		}

		const size_t left_bottom_index = current_level.length();
		const size_t pattern_length = 3;

		for (char letter = MIN_LETTER; letter <= MAX_LETTER; ++letter)
		{
			const string pattern = string(previous_level.substr(left_bottom_index, pattern_length - 1)) + letter;
			const bool pattern_is_allowed = allowed[get_mask(pattern)];

			if (!pattern_is_allowed)
			{
				continue;
			}

			current_level += letter;

			if (can_solve(previous_level, current_level, allowed, memo))
			{
				return true;
			}

			current_level.pop_back();
		}

		return false;
	}

	auto can_solve(const string& previous_level, unordered_map<string, bool>& memo, const vector<bool>& allowed) -> bool
	{
		const bool pyramid_is_complete = previous_level.length() == 1;

		if (pyramid_is_complete)
		{
			return true;
		}
        
        const bool solvability_is_already_known = memo.contains(previous_level);

        if (solvability_is_already_known)
        {
            return memo.at(previous_level);
        }

		string current_level;
		memo[previous_level] = can_solve(previous_level, current_level, allowed, memo);

        return memo.at(previous_level);
	}

public:
	auto pyramidTransition(string bottom, const vector<string>& allowed) -> bool
	{
        if (allowed.empty())
        {
            return false;
        }

        unordered_map<string, bool> memo;

		return can_solve(bottom, memo, find_allowed_patterns_masks(allowed));
	}
};
16900