algoadvance

Leetcode 756. Pyramid Transition Matrix

Problem Statement

You are given a string bottom, which represents the bottom row of a pyramid. You are also given a list of strings allowed, where each string represents a valid triple that can be used to build the pyramid from the bottom row.

You can use these triples to place a block on top of two adjacent blocks in the current row. Specifically, if you have blocks A and B in the current row (with A to the left of B), and there is a triple “ABC” in allowed, then you can place block C on top of blocks A and B.

Return true if you can build the pyramid from the bottom row to the top such that it results in a single block at the top. Otherwise, return false.

Example:

Input: bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
Output: true
Explanation:
   A
  / \
 G   E
/ \ / \
B   C   D

Input: bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
Output: false

Clarifying Questions

  1. Is it guaranteed that the allowed triples always represent valid block configurations?
  2. Can the bottom row contain any length of string, and does it always consist of uppercase letters?
  3. How large can the bottom row and allowed list become? (For time complexity estimation)

Strategy

  1. Data Structure:
    • Use a dictionary to store allowed triples for quick lookup.
  2. Recursive Approach with Memoization:
    • Use recursive backtracking to attempt building the pyramid from the given bottom row.
    • Use memoization to avoid recalculating the possibility of constructing sub-pyramids.
  3. Steps:
    1. Convert allowed list into a dictionary where keys are pairs (A, B) and values are lists of valid third blocks C.
    2. Define a recursive function that tries to build the pyramid layer-by-layer.
    3. If the current layer has only one block, return true since we built the pyramid.
    4. For each position in the current layer:
      • Try to form valid upper layers using the allowed triples.
      • Recur with the new layer.
    5. Use memoization to save results of previously computed subproblems to optimize.
import java.util.*;

public class PyramidTransition {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        // Build the map from pairs to possible tops
        Map<String, Set<Character>> map = new HashMap<>();
        for (String triple : allowed) {
            String base = triple.substring(0, 2);
            char top = triple.charAt(2);
            map.putIfAbsent(base, new HashSet<>());
            map.get(base).add(top);
        }
        
        // Memoization map
        Map<String, Boolean> memo = new HashMap<>();
        
        // Function to recursively check if we can build the pyramid
        return canBuildPyramid(bottom, map, memo);
    }

    private boolean canBuildPyramid(String bottom, Map<String, Set<Character>> map, Map<String, Boolean> memo) {
        if (bottom.length() == 1) {
            return true; // A single block as the top means we've successfully built the pyramid
        }
        
        // Check memo
        if (memo.containsKey(bottom)) {
            return memo.get(bottom);
        }
        
        // Attempt to build the next level
        List<String> nextLevels = new ArrayList<>();
        generateNextLevels(bottom, new StringBuilder(), 0, map, nextLevels);
        
        for (String nextLevel : nextLevels) {
            if (canBuildPyramid(nextLevel, map, memo)) {
                memo.put(bottom, true);
                return true;
            }
        }
        
        memo.put(bottom, false);
        return false;
    }

    private void generateNextLevels(String bottom, StringBuilder current, int index, Map<String, Set<Character>> map, List<String> nextLevels) {
        if (index == bottom.length() - 1) {
            nextLevels.add(current.toString());
            return;
        }
        
        String base = bottom.substring(index, index + 2);
        if (map.containsKey(base)) {
            for (char top : map.get(base)) {
                current.append(top);
                generateNextLevels(bottom, current, index + 1, map, nextLevels);
                current.deleteCharAt(current.length() - 1); // Backtrack
            }
        }
    }

    public static void main(String[] args) {
        PyramidTransition ptm = new PyramidTransition();
        String bottom1 = "BCD";
        List<String> allowed1 = Arrays.asList("BCG", "CDE", "GEA", "FFF");
        System.out.println(ptm.pyramidTransition(bottom1, allowed1)); // true

        String bottom2 = "AABA";
        List<String> allowed2 = Arrays.asList("AAA", "AAB", "ABA", "ABB", "BAC");
        System.out.println(ptm.pyramidTransition(bottom2, allowed2)); // false
    }
}

Time Complexity

Make sure to check the constraints for very large inputs to ensure the solution is feasible within the given limits.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI