756. Pyramid Transition Matrix #

Problem #

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 can't stack the pyramid to the top.
Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.

Note:

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

Problem Summary #

Now, we use some blocks to stack a pyramid. Each block is represented by a string containing only one letter, such as “Z”. The stacking rules of the pyramid are represented using triples as follows:

(A, B, C) means that “C” is the upper-level block, and blocks “A” and “B” are respectively the left and right child blocks of “C” on the layer below. If and only if (A, B, C) is an allowed triple, we can stack it.

Initially, given the base layer bottom of the pyramid, represented by a string, and a list of allowed triples allowed, where each triple is represented by a string of length 3. Return true if it is possible to stack from the base layer all the way to the top, otherwise return false.

Solution Approach #

This problem is a DFS problem. The problem gives the base string of the pyramid. It also gives a string array, where the strings in the array represent blocks. Each block is composed of 3 characters. The first two characters represent the bottom edge of the block, and the last character represents the top of the block. The question asks whether the given characters can form a pyramid. The characteristic of a pyramid is that there is only one character at the top.
Use DFS to deeply search each block, gradually stacking upward starting from the bottom-level blocks. With each recursive layer, the blocks at the bottom of the new layer will change. When the recursion reaches a layer where the bottom has only 2 characters and the top has only one character, it has reached the top of the pyramid and is considered complete. In order to select suitable blocks, use the 2 characters at the bottom of each block as the key and put them into a map to speed up lookup. The problem also gives a special case: the same bottom may have multiple kinds of blocks, so one key may correspond to multiple values, meaning there may be multiple possible top blocks. This situation needs to be considered during recursive traversal.

Code #


package leetcode

func pyramidTransition(bottom string, allowed []string) bool {
	pyramid := make(map[string][]string)
	for _, v := range allowed {
		pyramid[v[:len(v)-1]] = append(pyramid[v[:len(v)-1]], string(v[len(v)-1]))
	}
	return dfsT(bottom, "", pyramid)
}

func dfsT(bottom, above string, pyramid map[string][]string) bool {
	if len(bottom) == 2 && len(above) == 1 {
		return true
	}
	if len(bottom) == len(above)+1 {
		return dfsT(above, "", pyramid)
	}
	base := bottom[len(above) : len(above)+2]
	if data, ok := pyramid[base]; ok {
		for _, key := range data {
			if dfsT(bottom, above+key, pyramid) {
				return true
			}
		}
	}
	return false
}