Kotlin | LeetCode

Задача: 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⃣Начните с нижнего уровня пирамиды и используйте рекурсию для построения каждого следующего уровня, проверяя каждый треугольный узор на допустимость.

😎

Решение:

class Solution {
    fun pyramidTransition(bottom: String, allowed: List<String>): Boolean {
        val allowedDict = mutableMapOf<String, MutableList<Char>>()

        for (pattern in allowed) {
            val key = pattern.substring(0, 2)
            val value = pattern[2]
            allowedDict.computeIfAbsent(key) { mutableListOf() }.add(value)
        }

        return canBuild(bottom, allowedDict)
    }

    private fun canBuild(currentLevel: String, allowedDict: Map<String, List<Char>>): Boolean {
        if (currentLevel.length == 1) return true

        val nextLevelOptions = mutableListOf<List<Char>>()
        for (i in 0 until currentLevel.length - 1) {
            val key = currentLevel.substring(i, i + 2)
            if (!allowedDict.containsKey(key)) return false
            nextLevelOptions.add(allowedDict[key]!!)
        }

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

    private fun canBuildNextLevel(options: List<List<Char>>, index: Int, nextLevel: String, allowedDict: Map<String, List<Char>>): Boolean {
        if (index == options.size) return canBuild(nextLevel, allowedDict)
        for (option in options[index]) {
            if (canBuildNextLevel(options, index + 1, nextLevel + option, allowedDict)) return true
        }
        return false
    }
}

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

Please open Telegram to view this post