Pyramid Transition Matrix - Leetcode Solution

Problem Statement:

We are stacking blocks to form a pyramid. Each block has a color which is a one-letter string.

We are allowed to place any color block C on top of two adjacent blocks of colors A and B, if and only if ABC is an allowed triple.

We start with a bottom row of bottom, represented as a single string. We also start with a list of allowed triples allowed. Each allowed triple is represented as a string of length 3.

Return true if we can build the pyramid all the way to the top, otherwise false.

Example 1: Input: bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"] Output: true Explanation: We can stack the pyramid like this: A /
G E / \ /
B C D

We are allowed to place G on top of B and C because BCG is an allowed triple. Similarly, we can place E on top of C and D, then A on top of G and E.

Example 2: Input: bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"] Output: false Explanation: We cannot stack the pyramid to the top. Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.

Constraints:

1. bottom will be a string with length in range [2, 8].
2. allowed will have length in range [0, 200].
3. Letters in all strings will be chosen from the set {'A', 'B', 'C', 'D', 'E', 'F', 'G'}.

Solution:

The given problem can be solved using recursion and caching techniques. We can use a memoization table to memoize the intermediate results to avoid recomputation.

We will first create a mapping of all possible allowed triples. This can be done using a hashmap or set. Once we have the mapping, we will perform a recursive DFS starting from the bottom of the pyramid. At each level, we will consider all possible blocks that can be placed on top of the current level.

For each block, we will check if it forms an allowed triple with the adjacent blocks in the layer below. If it does, we will add it to the current level and recursively call the function with the new level.

If we reach the last level of the pyramid and we have a valid pyramid, we will return True. If we cannot find a valid pyramid, we will return False.

To optimize the solution, we can use a memoization table to store the intermediate results. We will use the memoization table to avoid recomputation of the same subproblems. The memoization table will store the current level and the index of the next block to be visited.

Time Complexity:

The time complexity of the above solution is O(n^n), where n is the length of the input string. The worst case scenario arises when all allowed triples are valid, and we have to explore all possible combinations.

Space Complexity:

The space complexity of the above solution is also O(n^n) due to the recursive DFS and caching. The memoization table will store O(n^2) entries, and each entry will store a string of length n. Thus, the total space required will be O(n^3).

Code:

The following is the code for the Pyramid Transition Matrix problem in Python:

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        mapping = collections.defaultdict(set)
        for a, b, c in allowed:
            mapping[(a, b)].add(c)

        memo = {}
        def dfs(level, next_level):
            if len(level) == 1:
                return True
            if (level, next_level) in memo:
                return memo[(level, next_level)]

            i = len(level) - len(next_level) - 1
            if len(mapping.get((level[i], level[i+1]), [])) == 0:
                memo[(level, next_level)] = False
                return False

            for c in mapping[(level[i], level[i+1])]:
                if i == len(next_level) - 1:
                    if dfs(next_level + c, ""):
                        memo[(level, next_level)] = True
                        return True
                else:
                    if dfs(level, next_level + c):
                        memo[(level, next_level)] = True
                        return True

            memo[(level, next_level)] = False
            return False

        return dfs(bottom, "")

The code first creates a mapping of all the allowed triples using a defaultdict of sets. It then defines the memoization table and the recursive DFS function.

The DFS function first checks if the current level is the last level of the pyramid. If it is, it returns True. If not, it checks the memoization table for the current level and the next level to be visited. If the result is already cached, it returns the cached result.

If the result is not cached, it computes the index of the next block to be visited. If there are no allowed triples that can be formed at this level, it returns False.

If there are allowed triples, it iterates through all the blocks that can be placed on top of the current level. If the iteration reaches the last block in this level, it recursively calls the DFS function with the new level and an empty next_level. If not, it recursively calls the DFS function with the same level and the updated next_level.

If a valid pyramid can be constructed, it caches the result and returns True. If not, it caches the result and returns False.

Thus, the above code provides a solution to the Pyramid Transition Matrix problem on LeetCode.

1