756. Pyramid Transition Matrix

LeetCode medium original: C# #csharp #hash-table #leetcode #matrix #medium #recursion #string #tree

Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.

LeetCode Static

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

Beispiel:

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

Output: true

C# Lösung

zugeordnet/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++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen

#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 Lösung

zugeordnet/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 Lösung

zugeordnet/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 Lösung

zugeordnet/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 Lösung

zugeordnet/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
}

Algorithm

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

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

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

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen

Es gibt noch keine aktiven Stellen.