Pyramid Transition Matrix

This approach significantly optimizes the brute-force backtracking by using memoization, a technique common in dynamic programming. The key observation is that the same intermediate row configuration can be reached from multiple different lower rows. Instead of re-computing whether a pyramid can be built from this intermediate row every time it's encountered, we can store the result the first time we compute it and look it up for subsequent encounters.

• Preprocessing: Convert the allowed list into a Map<String, List<Character>> for efficient lookups. The key is the 2-character base, and the value is a list of possible top blocks.
• Memoization: Use a Set<String> or Map<String, Boolean> to store the results for subproblems. A subproblem is identified by the string of a given row. We can store rows that are determined to be 'unsolvable'.
• Recursive Solver: Create a recursive function, solve(currentRow, memo), that checks if a pyramid can be built.
• Base Cases:
  • If currentRow.length() == 1, return true.
  • If currentRow is in the memoization table (meaning we've already proved it's unsolvable), return false.
• Recursive Step:
  • Use a helper function to generate and test possible next rows one character at a time. This helper function, say findPath(currentRow, nextRowBuilder, index, memo), will try to build a valid nextRow.
  • For each position in the nextRow, iterate through all possible characters. Recursively call findPath for the next position.
  • When a full nextRow is constructed, call solve(nextRow, memo).
  • If solve returns true, a path is found, so propagate true all the way up.
• Memoize Failures: If the findPath function explores all possibilities for currentRow and fails to find a solution, add currentRow to the memoization set before returning false.

We enhance the recursive solution by adding a cache (memoization table) to keep track of rows from which it's impossible to build a pyramid. This avoids redundant computations.

The algorithm is a top-down dynamic programming approach:

1. We preprocess the allowed list into a map for quick lookups, just like in the brute-force approach.
2. We use a Set<String> to store the rows that we have already processed and confirmed cannot lead to a valid pyramid top.
3. The main recursive function solve(currentRow) first checks its base cases: if the row is of length 1 (success) or if the row is already in our failure set (cached failure).
4. If it's a new row, we proceed to find a valid path upwards. We do this with a helper function that constructs the next row piece by piece. This helper tries every possible character for the first position of the next row, then for each of those, every possible character for the second, and so on.
5. Once a complete nextRow is formed, we recursively call solve on it.
6. If any of these recursive calls eventually return true, we have found a solution.
7. If, after trying all possible valid next rows, none lead to a solution, we add the currentRow to our failure set and return false.

This way, any given row configuration is fully explored only once. Subsequent calls with the same row will return the cached result instantly.

import java.util.*;

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, List<Character>> transitions = new HashMap<>();
        for (String s : allowed) {
            String key = s.substring(0, 2);
            transitions.computeIfAbsent(key, k -> new ArrayList<>()).add(s.charAt(2));
        }
        // Memoization set for rows that cannot form a pyramid
        Set<String> memo = new HashSet<>();
        return solve(bottom, transitions, memo);
    }

    private boolean solve(String currentRow, Map<String, List<Character>> transitions, Set<String> memo) {
        if (currentRow.length() == 1) {
            return true;
        }
        if (memo.contains(currentRow)) {
            return false;
        }

        boolean canMakePyramid = findPathForNextRow(currentRow, 0, new StringBuilder(), transitions, memo);
        
        if (!canMakePyramid) {
            memo.add(currentRow);
        }
        
        return canMakePyramid;
    }

    private boolean findPathForNextRow(String currentRow, int index, StringBuilder nextRowBuilder, Map<String, List<Character>> transitions, Set<String> memo) {
        if (index == currentRow.length() - 1) {
            // A complete next row has been formed, now solve for it
            return solve(nextRowBuilder.toString(), transitions, memo);
        }

        String key = currentRow.substring(index, index + 2);
        if (!transitions.containsKey(key)) {
            return false; // No transition possible, this path is invalid
        }

        for (char c : transitions.get(key)) {
            nextRowBuilder.append(c);
            if (findPathForNextRow(currentRow, index + 1, nextRowBuilder, transitions, memo)) {
                return true; // A valid pyramid was found down this path
            }
            nextRowBuilder.deleteCharAt(nextRowBuilder.length() - 1); // Backtrack
        }

        return false; // No character choice at this index led to a solution
    }
}