← Static tasks

756. Pyramid Transition Matrix

leetcode medium

#csharp#hash-table#leetcode#matrix#medium#recursion#string#tree

Task

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

Пример:

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

Output: true

C# solution

matched/original
public class Solution {
    public bool PyramidTransition(string bottom, IList<string> allowed) {
        var allowedDict = new Dictionary<string, List<char>>();
        
        foreach (var pattern in allowed) {
            var key = pattern.Substring(0, 2);
            var value = pattern[2];
            if (!allowedDict.ContainsKey(key)) {
                allowedDict[key] = new List<char>();
            }
            allowedDict[key].Add(value);
        }
        return CanBuild(bottom, allowedDict);
    }
    private bool CanBuild(string currentLevel, Dictionary<string, List<char>> allowedDict) {
        if (currentLevel.Length == 1) return true;
        var nextLevelOptions = new List<List<char>>();
        for (int i = 0; i < currentLevel.Length - 1; i++) {
            var key = currentLevel.Substring(i, 2);
            if (!allowedDict.ContainsKey(key)) return false;
            nextLevelOptions.Add(allowedDict[key]);
        }
        return CanBuildNextLevel(nextLevelOptions, 0, "", allowedDict);
    }
    private bool CanBuildNextLevel(List<List<char>> options, int index, string nextLevel, Dictionary<string, List<char>> allowedDict) {
        if (index == options.Count) return CanBuild(nextLevel, allowedDict);
        foreach (var option in options[index]) {
            if (CanBuildNextLevel(options, index + 1, nextLevel + option, allowedDict)) return true;
        }
        return false;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool PyramidTransition(string bottom, vector<string> allowed) {
        var allowedDict = new unordered_map<string, List<char>>();
        
        foreach (var pattern in allowed) {
            var key = pattern.Substring(0, 2);
            var value = pattern[2];
            if (!allowedDict.count(key)) {
                allowedDict[key] = new List<char>();
            }
            allowedDict[key].push_back(value);
        }
        return CanBuild(bottom, allowedDict);
    }
    private bool CanBuild(string currentLevel, unordered_map<string, List<char>> allowedDict) {
        if (currentLevel.size() == 1) return true;
        var nextLevelOptions = new List<List<char>>();
        for (int i = 0; i < currentLevel.size() - 1; i++) {
            var key = currentLevel.Substring(i, 2);
            if (!allowedDict.count(key)) return false;
            nextLevelOptions.push_back(allowedDict[key]);
        }
        return CanBuildNextLevel(nextLevelOptions, 0, "", allowedDict);
    }
    private bool CanBuildNextLevel(List<List<char>> options, int index, string nextLevel, unordered_map<string, List<char>> allowedDict) {
        if (index == options.size()) return CanBuild(nextLevel, allowedDict);
        foreach (var option in options[index]) {
            if (CanBuildNextLevel(options, index + 1, nextLevel + option, allowedDict)) return true;
        }
        return false;
    }
}

Java solution

matched/original
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;
    }

JavaScript solution

matched/original
var pyramidTransition = function(bottom, allowed) {
    let allowedDict = {};

    for (let pattern of allowed) {
        let key = pattern.slice(0, 2);
        if (!(key in allowedDict)) {
            allowedDict[key] = [];
        }
        allowedDict[key].push(pattern[2]);
    }

    function canBuild(currentLevel) {
        if (currentLevel.length == 1) return true;

        let nextLevelOptions = [];
        for (let i = 0; i < currentLevel.length - 1; i++) {
            let key = currentLevel.slice(i, i + 2);
            if (!(key in allowedDict)) return false;
            nextLevelOptions.push(allowedDict[key]);
        }

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

    function canBuildNextLevel(options, index, nextLevel) {
        if (index == options.length) return canBuild(nextLevel);
        for (let option of options[index]) {
            if (canBuildNextLevel(options, index + 1, nextLevel + option)) return true;
        }
        return false;
    }

    return canBuild(bottom);
};

Python solution

matched/original
def pyramidTransition(bottom, allowed):
    from collections import defaultdict

    allowed_dict = defaultdict(list)
    for pattern in allowed:
        allowed_dict[pattern[:2]].append(pattern[2])

    def can_build(current_level):
        if len(current_level) == 1:
            return True
        next_level = []
        for i in range(len(current_level) - 1):
            if current_level[i:i+2] not in allowed_dict:
                return False
            next_level.append(allowed_dict[current_level[i:i+2]])
        return any(can_build("".join(c)) for c in product(*next_level))

    return can_build(bottom)

Go solution

matched/original
package main

func pyramidTransition(bottom string, allowed []string) bool {
    allowedDict := make(map[string][]byte)

    for _, pattern := range allowed {
        key := pattern[:2]
        value := pattern[2]
        allowedDict[key] = append(allowedDict[key], value)
    }

    return canBuild(bottom, allowedDict)
}

func canBuild(currentLevel string, allowedDict map[string][]byte) bool {
    if len(currentLevel) == 1 {
        return true
    }

    nextLevelOptions := [][]byte{}
    for i := 0; i < len(currentLevel)-1; i++ {
        key := currentLevel[i : i+2]
        if options, exists := allowedDict[key]; exists {
            nextLevelOptions = append(nextLevelOptions, options)
        } else {
            return false
        }
    }

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

func canBuildNextLevel(options [][]byte, index int, nextLevel string, allowedDict map[string][]byte) bool {
    if index == len(options) {
        return canBuild(nextLevel, allowedDict)
    }
    for _, option := range options[index] {
        if canBuildNextLevel(options, index+1, nextLevel+string(option), allowedDict) {
            return true
        }
    }
    return false
}

Explanation

Algorithm

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

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

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

😎