Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/756.html

756. Pyramid Transition Matrix

Level

Medium

Description

We are stacking blocks to form a pyramid. Each block has a color which is a one letter string.

We are allowed to place any color block C on top of two adjacent blocks of colors A and B, if and only if ABC is an allowed triple.

We start with a bottom row of bottom, represented as a single string. We also start with a list of allowed triples allowed. Each allowed triple is represented as a string of length 3.

Return true if we can build the pyramid all the way to the top, otherwise false.

Example 1:

Input: bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
Output: true
Explanation:
We can stack the pyramid like this:
    A
   / \
  G   E
 / \ / \
B   C   D

We are allowed to place G on top of B and C because BCG is an allowed triple.  Similarly, we can place E on top of C and D, then A on top of G and E.

Example 2:

Input: bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
Output: false
Explanation:
We can't stack the pyramid to the top.
Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.

Note:

  1. bottom will be a string with length in range [2, 8].
  2. allowed will have length in range [0, 200].
  3. Letters in all strings will be chosen from the set {'A', 'B', 'C', 'D', 'E', 'F', 'G'}.

Solution

First convert the list allowed to a map, which maps a string of length 2 to a character that is allowed in an allowed triple.

Then do recursion. Each time an upper level’s string is obtained, do recursion until the top level is met. In this case, return true. If it is not possible to reach the top level using allowed triples, return false.

  • class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        if (bottom == null || bottom.length() == 0)
            return false;
        if (bottom.length() == 1)
            return true;
        Map<String, Set<Character>> allowedMap = new HashMap<String, Set<Character>>();
        for (String str : allowed) {
            String key = str.substring(0, 2);
            char value = str.charAt(2);
            Set<Character> allowedSet = allowedMap.getOrDefault(key, new HashSet<Character>());
            allowedSet.add(value);
            allowedMap.put(key, allowedSet);
        }
        return pyramidTransition(bottom, allowedMap);
    }

    public boolean pyramidTransition(String bottom, Map<String, Set<Character>> allowedMap) {
        int length = bottom.length();
        if (length == 1)
            return true;
        List<String> next = new ArrayList<String>();
        for (int i = 0; i < length - 1; i++) {
            String substr = bottom.substring(i, i + 2);
            if (!allowedMap.containsKey(substr))
                return false;
            else {
                int size = next.size();
                if (size == 0) {
                    Set<Character> set = allowedMap.get(substr);
                    for (char letter : set)
                        next.add(String.valueOf(letter));
                } else{
                    while (size > 0) {
                        Set<Character> set = allowedMap.get(substr);
                        for (char letter : set)
                            next.add(next.get(0) + letter);
                        next.remove(0);
                        size--;
                    }
                }
            }
        }
        for (String str : next) {
            if (pyramidTransition(str, allowedMap))
                return true;
        }
        return false;
    }
}

  • // OJ: https://leetcode.com/problems/pyramid-transition-matrix/
// Time: O(7^B)
// Space: O(A+7^B)
class Solution {
    vector<char> next[7][7] = {};
    vector<string> formNextLevel(string &bottom) {
        vector<string> ans{""};
        for (int i = 1; i < bottom.size(); ++i) {
            auto &n = next[bottom[i - 1] - 'A'][bottom[i] - 'A'];
            vector<string> v;
            for (char c : n) {
                for (auto &s : ans) {
                    if (s.empty() || next[s.back() - 'A'][c - 'A'].size()) v.push_back(s + c);
                }
            }
            swap(v, ans);
        }
        return ans;
    }
    bool dfs(string &bottom) {
        if (bottom.size() == 1) return true;
        for (auto &s : formNextLevel(bottom)) {
            if (dfs(s)) return true;
        }
        return false;
    }
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        for (auto &s : allowed) next[s[0] - 'A'][s[1] - 'A'].push_back(s[2]);
        return dfs(bottom);
    }
};

  • class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        @cache
        def dfs(s):
            if len(s) == 1:
                return True
            t = []
            for a, b in pairwise(s):
                cs = d[a, b]
                if not cs:
                    return False
                t.append(cs)
            return any(dfs(''.join(nxt)) for nxt in product(*t))

        d = defaultdict(list)
        for a, b, c in allowed:
            d[a, b].append(c)
        return dfs(bottom)

############

class Solution(object):
    def pyramidTransition(self, bottom, allowed):
        """
        :type bottom: str
        :type allowed: List[str]
        :rtype: bool
        """
        m = collections.defaultdict(list)
        for triples in allowed:
            m[triples[:2]].append(triples[-1])
        return self.helper(bottom, "", m)
        
    def helper(self, curr, above, m):
        if len(curr) == 2 and len(above) == 1:
            return True
        if len(above) == len(curr) - 1:
            return self.helper(above, "", m)
        pos = len(above)
        base = curr[pos : pos+2]
        if base in m:
            for ch in m[base]:
                if self.helper(curr, above + ch, m):
                    return True
        return False

All Problems

All Solutions