Google
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. 1.
    bottomwill be a string with length in range[2, 8].
  2. 2.
    allowedwill have length in range[0, 200].
  3. 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)