## 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:trueExplanation: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:falseExplanation: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'}`

.

## Rust Solution

```
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);
}
```

Having problems with this solution? Click here to submit an issue on github.