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]
.{'A', 'B', 'C', 'D', 'E', 'F', 'G'}
.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);
}