756. Pyramid Transition Matrix LeetCode Solution

In this guide, you will get 756. Pyramid Transition Matrix LeetCode Solution with the best time and space complexity. The solution to Pyramid Transition Matrix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Pyramid Transition Matrix solution in C++
  4. Pyramid Transition Matrix solution in Java
  5. Pyramid Transition Matrix solution in Python
  6. Additional Resources
756. Pyramid Transition Matrix LeetCode Solution image

Problem Statement of 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.

See also  1041. Robot Bounded In Circle LeetCode Solution

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.

Complexity Analysis

  • Time Complexity:
  • Space Complexity:

756. Pyramid Transition Matrix LeetCode Solution in C++

class Solution {
 public:
  bool pyramidTransition(string bottom, vector<string>& allowed) {
    unordered_map<string, vector<char>> prefixToBlocks;

    for (const string& a : allowed)
      prefixToBlocks[a.substr(0, 2)].push_back(a[2]);

    return dfs(bottom, "", 0, prefixToBlocks);
  }

 private:
  bool dfs(const string& row, const string& nextRow, int i,
           const unordered_map<string, vector<char>>& prefixToBlocks) {
    if (row.length() == 1)
      return true;
    if (nextRow.length() + 1 == row.length())
      return dfs(nextRow, "", 0, prefixToBlocks);

    const string& prefix = row.substr(i, 2);

    if (const auto it = prefixToBlocks.find(prefix);
        it != prefixToBlocks.cend())
      for (const char c : it->second)
        if (dfs(row, nextRow + c, i + 1, prefixToBlocks))
          return true;

    return false;
  }
};
/* code provided by PROGIEZ */

756. Pyramid Transition Matrix LeetCode Solution in Java

class Solution {
  public boolean pyramidTransition(String bottom, List<String> allowed) {
    Map<String, List<Character>> prefixToBlocks = new HashMap<>();

    for (final String a : allowed) {
      final String lowerBlocks = a.substring(0, 2);
      prefixToBlocks.putIfAbsent(lowerBlocks, new LinkedList<>());
      prefixToBlocks.get(lowerBlocks).add(a.charAt(2));
    }

    return dfs(bottom, "", 0, prefixToBlocks);
  }

  private boolean dfs(final String row, final String nextRow, int i,
                      Map<String, List<Character>> prefixToBlocks) {
    if (row.length() == 1)
      return true;
    if (nextRow.length() + 1 == row.length())
      return dfs(nextRow, "", 0, prefixToBlocks);

    final String prefix = row.substring(i, i + 2);

    if (prefixToBlocks.containsKey(prefix))
      for (final char c : prefixToBlocks.get(prefix))
        if (dfs(row, nextRow + c, i + 1, prefixToBlocks))
          return true;

    return false;
  }
}
// code provided by PROGIEZ

756. Pyramid Transition Matrix LeetCode Solution in Python

class Solution:
  def pyramidTransition(self, bottom: str, allowed: list[str]) -> bool:
    prefixToBlocks = collections.defaultdict(list)

    for a in allowed:
      prefixToBlocks[a[:2]].append(a[2])

    def dfs(row: str, nextRow: str, i: int) -> bool:
      if len(row) == 1:
        return True
      if len(nextRow) + 1 == len(row):
        return dfs(nextRow, '', 0)

      for c in prefixToBlocks[row[i:i + 2]]:
        if dfs(row, nextRow + c, i + 1):
          return True

      return False

    return dfs(bottom, '', 0)
# code by PROGIEZ

Additional Resources

See also  74. Search a 2D Matrix LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.