756. Pyramid Transition Matrix

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.

 

Constraints:

  • 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'}.

756. Pyramid Transition Matrix
struct Solution;

use std::collections::HashSet;

impl Solution {
    fn pyramid_transition(bottom: String, allowed: Vec<String>) -> bool {
        let n = bottom.len();
        let mut v: Vec<Vec<usize>> = vec![vec![]; n];
        let mut map: Vec<Vec<HashSet<usize>>> = vec![vec![HashSet::new(); 7]; 7];
        for c in bottom.bytes() {
            let b = (c - b'A') as usize;
            v[n - 1].push(b);
        }
        for s in allowed {
            let s: Vec<u8> = s.bytes().collect();
            let a: usize = (s[0] - b'A') as usize;
            let b: usize = (s[1] - b'A') as usize;
            let c: usize = (s[2] - b'A') as usize;
            map[a][b].insert(c);
        }
        Self::backtrack(&mut v, &map, n - 1, n - 1)
    }

    fn backtrack(
        v: &mut Vec<Vec<usize>>,
        map: &[Vec<HashSet<usize>>],
        row: usize,
        col: usize,
    ) -> bool {
        if row == 0 {
            return true;
        }
        let (r, c) = if col == row {
            (row - 1, 0)
        } else {
            (row, col + 1)
        };
        let left = v[r + 1][c];
        let right = v[r + 1][c + 1];
        for &x in &map[left][right] {
            v[r].push(x);
            if Self::backtrack(v, map, r, c) {
                return true;
            }
            v[r].pop();
        }
        false
    }
}

#[test]
fn test() {
    let bottom = "ABC".to_string();
    let allowed: Vec<String> = vec_string!["ABD", "BCE", "DEF", "FFF"];
    Solution::pyramid_transition(bottom, allowed);
}