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:
bottomwill be a string with length in range[2, 8].allowedwill have length in range[0, 200].- 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 -
func pyramidTransition(bottom string, allowed []string) bool { f := make([][]int, 7) for i := range f { f[i] = make([]int, 7) } for _, s := range allowed { a, b := s[0]-'A', s[1]-'A' f[a][b] |= 1 << (s[2] - 'A') } dp := map[string]bool{} var dfs func(s string, t []byte) bool dfs = func(s string, t []byte) bool { if len(s) == 1 { return true } if len(t)+1 == len(s) { return dfs(string(t), []byte{}) } k := s + "." + string(t) if v, ok := dp[k]; ok { return v } a, b := s[len(t)]-'A', s[len(t)+1]-'A' cs := f[a][b] for i := 0; i < 7; i++ { if ((cs >> i) & 1) == 1 { t = append(t, byte('A'+i)) if dfs(s, t) { dp[k] = true return true } t = t[:len(t)-1] } } dp[k] = false return false } return dfs(bottom, []byte{}) }