LeetCode Entry

756. Pyramid Transition Matrix

29.12.2025 medium 2025 kotlin rust

Can build a pyramid from transitions?

756. Pyramid Transition Matrix medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1219

Problem TLDR

Can build a pyramid from transitions? #medium #backtracking

Intuition

DFS for each row. DFS with backtracking for each transition character in the row.

Approach

• speedup with arena allocation

• speedup with Int keys: A«16

  B

• speedup with transitions matrix bitset: M[A][B] = bitmask
• speedup with HashSet of bad keys

Complexity

• Time complexity: \(O(b^a)\)

• Space complexity: \(O(b^2)\)

Code

// 15ms
    fun pyramidTransition(b: String, a: List<String>): Boolean {
        val m = IntArray(26 * 26); var j = b.length; val bad = HashSet<Long>()
        val r = IntArray(j * (j + 1) / 2) { b[it % j] - 'A' }
        for (s in a) { val x = s[0]-'A'; val y = s[1]-'A'; m[x*26+y] = m[x*26+y] or (1 shl (s[2]-'A'))}
        fun dfs(st: Int, sz: Int, key: Long): Boolean {
            if (j == r.size) return true; if (key in bad) return false
            if (j == st + sz + 1 + sz) return dfs(j - sz, sz - 1, key)
            var mask = m[r[j - sz - 1] * 26 + r[j - sz]]
            while (mask > 0) {
                val c = mask.countTrailingZeroBits(); mask = mask and (mask - 1); r[j++] = c
                if (dfs(st, sz, key or (c.toLong() shl ((j-st-sz)*5)))) return true; --j
            }
            bad.add(key); return false
        }
        return dfs(0, j - 1, 0)
    }

// 400ms
    fun pyramidTransition(b: String, a: List<String>): Boolean {
        val a = a.groupBy({ it.take(2) },{it[2]})
        fun dfs(b: List<Char>): Boolean {
            val r = ArrayList<Char>()
            fun dfs2(i: Int): Boolean = if (i == b.size) dfs(r) else a["${b[i-1]}${b[i]}"]
                ?.any { r += it; val n = dfs2(i+1); r.removeLast(); n } == true
            return b.size == 1 || dfs2(1)
        }
        return dfs(b.toList())
    }

// 0ms
    pub fn pyramid_transition(b: String, a: Vec<String>) -> bool {
        let (mut m, mut j, mut bad) = ([0u32; 26 * 26], b.len(), HashSet::<u64>::new());
        for s in a { let t = s.as_bytes(); m[(t[0]-b'A')as usize*26 + (t[1]-b'A')as usize] |= 1u32<<(t[2]-b'A')}
        let mut r = vec![0u8; j*(j+1)/2]; for (i,&c) in b.as_bytes().iter().enumerate() {r[i] = c - b'A'}
        fn dfs(m: &[u32; 26 * 26], r: &mut [u8], j: &mut usize, st: usize, sz: usize, key: u64, bad: &mut HashSet<u64>) -> bool {
            if *j == r.len() { return true }; if *j == st+sz+1+sz { return dfs(m, r, j, *j-sz, sz-1, key, bad)}
            if bad.contains(&key) { return false }
            let mut mask = m[r[*j - sz - 1] as usize * 26 + r[*j - sz] as usize];
            while mask != 0 {
                let c = mask.trailing_zeros() as u8; mask &= mask - 1; r[*j] = c; *j += 1;
                if dfs(m, r, j, st, sz, key | ((c as u64) << ((*j-st-sz-2)*5)), bad) { return true }; *j -= 1;
            }
            bad.insert(key); false
        }
        dfs(&m, &mut r, &mut j, 0, b.len() - 1, 0, &mut bad)
    }