Задача: 756. Pyramid Transition Matrix
Сложность: medium

Вы складываете блоки так, чтобы получилась пирамида. Каждый блок имеет цвет, который представлен одной буквой. Каждый ряд блоков содержит на один блок меньше, чем ряд под ним, и располагается по центру сверху. Чтобы пирамида выглядела эстетично, допускаются только определенные треугольные узоры. Треугольный узор состоит из одного блока, уложенного поверх двух блоков. Шаблоны задаются в виде списка допустимых трехбуквенных строк, где первые два символа шаблона представляют левый и правый нижние блоки соответственно, а третий символ - верхний блок. Например, "ABC" представляет треугольный шаблон с блоком 'C', уложенным поверх блоков 'A' (слева) и 'B' (справа). Обратите внимание, что это отличается от "BAC", где "B" находится слева внизу, а "A" - справа внизу. Вы начинаете с нижнего ряда блоков bottom, заданного в виде одной строки, который вы должны использовать в качестве основания пирамиды. Учитывая bottom и allowed, верните true, если вы можете построить пирамиду до самой вершины так, чтобы каждый треугольный узор в пирамиде был в allowed, или false в противном случае.

Пример:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true

👨‍💻 Алгоритм:

1⃣Создайте структуру данных для хранения допустимых треугольных узоров.

2⃣Напишите рекурсивную функцию, которая проверяет возможность построения следующего уровня пирамиды.

3⃣Начните с нижнего уровня пирамиды и используйте рекурсию для построения каждого следующего уровня, проверяя каждый треугольный узор на допустимость.

😎 Решение:

import java.util.*;

public class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, List<Character>> allowedDict = new HashMap<>();
        
        for (String pattern : allowed) {
            String key = pattern.substring(0, 2);
            char value = pattern.charAt(2);
            allowedDict.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
        }

        return canBuild(bottom, allowedDict);
    }

    private boolean canBuild(String currentLevel, Map<String, List<Character>> allowedDict) {
        if (currentLevel.length() == 1) return true;

        List<List<Character>> nextLevelOptions = new ArrayList<>();
        for (int i = 0; i < currentLevel.length() - 1; i++) {
            String key = currentLevel.substring(i, i + 2);
            if (!allowedDict.containsKey(key)) return false;
            nextLevelOptions.add(allowedDict.get(key));
        }

        return canBuildNextLevel(nextLevelOptions, 0, "", allowedDict);
    }

    private boolean canBuildNextLevel(List<List<Character>> options, int index, String nextLevel, Map<String, List<Character>> allowedDict) {
        if (index == options.size()) return canBuild(nextLevel, allowedDict);
        for (char option : options.get(index)) {
            if (canBuildNextLevel(options, index + 1, nextLevel + option, allowedDict)) return true;
        }
        return false;
    }

Ставь 👍 и забирай 📚 Базу знаний