756 Pyramid Transition Matrix

756. Pyramid Transition Matrix​
1. Question
We are stacking blocks to form a pyramid. Each block has a color which is a one letter string, like `'Z'`.
For every block of color `C` we place not in the bottom row, we are placing it on top of a left block of color `A` and right block of color `B`. We are allowed to place the block there only if `(A, B, C)` is an allowed triple.
We start with a bottom row ofbottom, represented as a single string. We also start with a list of allowed triplesallowed. 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:
1
Input: bottom = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]
2
​
3
Output: true
4
​
5
Explanation:
6
​
7
We can stack the pyramid like this:
8
    A
9
   / \
10
  D   E
11
 / \ / \
12
X   Y   Z
13
​
14
This works because ('X', 'Y', 'D'), ('Y', 'Z', 'E'), and ('D', 'E', 'A') are allowed triples.
Copied!
Example 2:
1
Input: bottom = "XXYX", allowed = ["XXX", "XXY", "XYX", "XYY", "YXZ"]
2
​
3
Output: false
4
​
5
Explanation:
6
​
7
We can't stack the pyramid to the top.
8
Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.
Copied!
Note:
1.bottomwill be a string with length in range[2, 8].
2.allowedwill have length in range[0, 200].
3.Letters in all strings will be chosen from the set{'A', 'B', 'C', 'D', 'E', 'F', 'G'}.
2. Implementation
(1) DFS + HashMap
思路:
(1) 根据题意，从bottom level根据allowed的string搭建金字塔，由于上一层里能放的character都要根据下一层的两个character决定，所以我们首先通过HashMap建立allowed string前两个character和最后一个character的映射关系
(2) 第二步就是通过DFS搭建金字塔，递归函数的参数定义分别是curLevel代表当前一层，lastLevel代表上一层，map则是第一步构造的HashMap. 如果当前一层的size为2，上一层的size为1，说明我们已经到塔顶，return true. 如果上一层的size比当前层少1，说明上一层已经搭好，我们要搭上上一层。在搭建上一层的过程中，我们先取到上一层待搭建的位置index，然后根据这个index在当前层中通过hashmap找到可以放置的character，递归实现
1
class Solution {
2
    public boolean pyramidTransition(String bottom, List<String> allowed) {
3
        Map<String, Set<Character>> map = new HashMap<>();
4
​
5
        for (String s : allowed) {
6
            String key = s.substring(0, 2);
7
            if (!map.containsKey(key)) {
8
                map.put(key, new HashSet<>());
9
            }
10
            map.get(key).add(s.charAt(2));
11
        }
12
        return canReachTop(bottom, "", map);
13
    }
14
​
15
    public boolean canReachTop(String curLevel, String lastLevel, Map<String, Set<Character>> map) {
16
        if (curLevel.length() == 2 && lastLevel.length() == 1) {
17
            return true;
18
        }
19
​
20
        if (lastLevel.length() == curLevel.length() - 1) {
21
            return canReachTop(lastLevel, "", map);
22
        }
23
​
24
        int index = lastLevel.length();
25
        String key = curLevel.substring(index, index + 2);
26
​
27
        if (map.containsKey(key)) {
28
            for (char c : map.get(key)) {
29
                if (canReachTop(curLevel, lastLevel + c, map)) {
30
                    return true;
31
                }
32
            }
33
        }
34
        return false;
35
    }
36
​
37
}
Copied!
3. Time & Space Complexity
时间复杂度O(n^2 + m),n是bottom的长度，从底层到顶层需要的character个数为n + (n - 1) + (n - 2) +... + 1=>O(n^2), m是allowed string的个数，构建hashMap需要O(m)的长度， 空间复杂度O(m + n^2), 递归深度是n^2, hashMap空间复杂度是O(m)

31 Next Permutation

753 Cracking the Safe

Last modified 2yr ago

Copy link

Contents

756. Pyramid Transition Matrix

1. Question

2. Implementation

3. Time & Space Complexity

756. Pyramid Transition Matrix​

1. Question

2. Implementation

3. Time & Space Complexity

756. Pyramid Transition Matrix