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

pyramidTransition.js

/**
 * @param {string} bottom
 * @param {string[]} allowed
 * @return {boolean}
 */
var pyramidTransition = function(bottom, allowed) {
    // STEP 1: Build a mapping from (left,right) -> list of possible tops
    // Example: "ABC" means A+B -> C
    const map = new Map();
    for (let pattern of allowed) {
        const left = pattern[0];
        const right = pattern[1];
        const top = pattern[2];
        const key = left + right;

        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key).push(top);
    }

    // Memoization: store rows that we've already determined cannot lead to a solution
    const badRows = new Set();

    // STEP 2: DFS function that tries to build the pyramid from a given row
    function canBuild(row) {
        // Base case: if row length is 1, we've reached the top successfully
        if (row.length === 1) return true;

        // If we've already seen this row and know it fails, skip it
        if (badRows.has(row)) return false;

        // STEP 3: Generate all possible next rows
        const allNextRows = [];

        // Helper to recursively build all combinations for the next row
        function buildNextRow(index, current) {
            // If we've assigned a block for every pair, we have a full next row
            if (index === row.length - 1) {
                allNextRows.push(current);
                return;
            }

            const pair = row[index] + row[index + 1];
            const options = map.get(pair);

            // If no allowed pattern for this pair, this row is a dead end
            if (!options) return;

            // Try each possible top block for this pair
            for (let top of options) {
                buildNextRow(index + 1, current + top);
            }
        }

        buildNextRow(0, "");

        // STEP 4: Try each possible next row recursively
        for (let nextRow of allNextRows) {
            if (canBuild(nextRow)) {
                return true;
            }
        }

        // If none worked, mark this row as bad and return false
        badRows.add(row);
        return false;
    }

    // Start DFS from the bottom row
    return canBuild(bottom);
};