756. Pyramid Transition Matrix

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 given as a list of three-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:

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:

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.

From: LeetCode
Link: 756. Pyramid Transition Matrix

---

Solution:

Ideas:

1. Memoization: Cache results for each level string to avoid recomputing the same subproblems

2. Preprocessing: Build a lookup table patterns[left][right] that directly gives all possible top blocks for any pair of bottom blocks

3. Efficient Lookup: Instead of scanning through all allowed patterns each time, use O(1) array access

Code:

// Hash table for memoization
#define HASH_SIZE 10000

typedef struct HashNode {
    char key[8];  // Max 7 chars + null terminator
    bool value;
    bool computed;
    struct HashNode* next;
} HashNode;

HashNode* hashTable[HASH_SIZE];

// Simple hash function
unsigned int hash(char* str) {
    unsigned int hash = 5381;
    while (*str) {
        hash = ((hash << 5) + hash) + *str++;
    }
    return hash % HASH_SIZE;
}

// Get memoized result
bool getMemo(char* key, bool* result) {
    unsigned int index = hash(key);
    HashNode* node = hashTable[index];
    
    while (node) {
        if (strcmp(node->key, key) == 0) {
            if (node->computed) {
                *result = node->value;
                return true;
            }
            return false;
        }
        node = node->next;
    }
    return false;
}

// Set memoized result
void setMemo(char* key, bool value) {
    unsigned int index = hash(key);
    HashNode* node = hashTable[index];
    
    // Check if key already exists
    while (node) {
        if (strcmp(node->key, key) == 0) {
            node->value = value;
            node->computed = true;
            return;
        }
        node = node->next;
    }
    
    // Create new node
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    strcpy(newNode->key, key);
    newNode->value = value;
    newNode->computed = true;
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

// Clear hash table
void clearMemo() {
    for (int i = 0; i < HASH_SIZE; i++) {
        HashNode* node = hashTable[i];
        while (node) {
            HashNode* temp = node;
            node = node->next;
            free(temp);
        }
        hashTable[i] = NULL;
    }
}

bool pyramidTransition(char* bottom, char** allowed, int allowedSize) {
    // Clear memoization table
    clearMemo();
    
    int bottomLen = strlen(bottom);
    
    // Preprocess allowed patterns for faster lookup
    // patterns[i][j] contains all possible top blocks for bottom pair (i,j)
    char patterns[6][6][7]; // 6 letters (A-F), max 6 possibilities each
    int patternCount[6][6];
    
    // Initialize
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            patternCount[i][j] = 0;
        }
    }
    
    // Build lookup table
    for (int i = 0; i < allowedSize; i++) {
        int left = allowed[i][0] - 'A';
        int right = allowed[i][1] - 'A';
        int top = allowed[i][2] - 'A';
        
        if (left >= 0 && left < 6 && right >= 0 && right < 6 && top >= 0 && top < 6) {
            patterns[left][right][patternCount[left][right]++] = 'A' + top;
        }
    }
    
    // Recursive function with memoization
    bool solve(char* level, int size) {
        // Check memoization
        bool result;
        if (getMemo(level, &result)) {
            return result;
        }
        
        // Base case
        if (size == 1) {
            setMemo(level, true);
            return true;
        }
        
        char nextLevel[7];
        int nextSize = size - 1;
        
        // Backtracking function
        bool fillLevel(int pos) {
            if (pos == nextSize) {
                nextLevel[pos] = '\0';
                return solve(nextLevel, nextSize);
            }
            
            int left = level[pos] - 'A';
            int right = level[pos + 1] - 'A';
            
            if (left < 0 || left >= 6 || right < 0 || right >= 6) {
                return false;
            }
            
            // Try each possible top block for this pair
            for (int i = 0; i < patternCount[left][right]; i++) {
                nextLevel[pos] = patterns[left][right][i];
                if (fillLevel(pos + 1)) {
                    return true;
                }
            }
            
            return false;
        }
        
        bool canBuild = fillLevel(0);
        setMemo(level, canBuild);
        return canBuild;
    }
    
    bool result = solve(bottom, bottomLen);
    clearMemo();
    return result;
}