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 - b'A') as usize;
let b: usize = (s - b'A') as usize;
let c: usize = (s - 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);
}
``````