LeetCode: Pyramid Transition Matrix

Pyramid Transition Matrix

Similar Problems:

• CheatSheet: Leetcode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups
• Tag: #bitmanipulation, #combination, #backtracking

We are stacking blocks to form a pyramid. Each block has a color which is a one letter string, like `’Z’`.

For every block of color `C` we place not in the bottom row, we are placing it on top of a left block of color `A` and right block of color `B`. We are allowed to place the block there only if `(A, B, C)` 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 = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]
Output: true
Explanation:
We can stack the pyramid like this:
    A
   / \
  D   E
 / \ / \
X   Y   Z

This works because ('X', 'Y', 'D'), ('Y', 'Z', 'E'), and ('D', 'E', 'A') are allowed triples.

Example 2:

Input: bottom = "XXYX", allowed = ["XXX", "XXY", "XYX", "XYY", "YXZ"]
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:

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’}.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:

// https://code.dennyzhang.com/pyramid-transition-matrix
// Basic Ideas: backtracking
//
// Notice: assume no duplicate allowed entries
//
// Complexity: Time O(k^n), Space O(n)
func dfs(pos int, chars []byte, nexts []byte, m map[string][]byte) bool {
    // Can form a final result or caculate next level
    if pos == len(chars)-1 {
        if len(nexts) == 1 {
            return true
        } else {
            // try with next level
            nexts2 := make([]byte, len(nexts))
            copy(nexts2, nexts)
            return dfs(0, nexts2, []byte{}, m)
        }
    }
    str := string(chars[pos])+string(chars[pos+1])
    l, ok := m[str]
    if !ok {
        return false
    }
    for _, b := range l {
        nexts = append(nexts, b)
        if dfs(pos+1, chars, nexts, m) {
            return true
        }
        nexts = nexts[0:len(nexts)-1]
    }
    return false
}

func pyramidTransition(bottom string, allowed []string) bool {
    m := map[string][]byte{}
    for _, str := range allowed {
        k, v := str[0:2], str[2]
        m[k] = append(m[k], v)
    }
    return dfs(0, []byte(bottom), []byte{}, m)
}