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:

Input: bottom = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]

Output: true

Explanation:

We can stack the pyramid like this:
    A
   / \
  D   E
 / \ / \
X   Y   Z

This works because ('X', 'Y', 'D'), ('Y', 'Z', 'E'), and ('D', 'E', 'A') are allowed triples.

Example 2:

Input: bottom = "XXYX", allowed = ["XXX", "XXY", "XYX", "XYY", "YXZ"]

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. 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，递归实现

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, Set<Character>> map = new HashMap<>();

        for (String s : allowed) {
            String key = s.substring(0, 2);
            if (!map.containsKey(key)) {
                map.put(key, new HashSet<>());
            }
            map.get(key).add(s.charAt(2));
        }
        return canReachTop(bottom, "", map);
    }

    public boolean canReachTop(String curLevel, String lastLevel, Map<String, Set<Character>> map) {
        if (curLevel.length() == 2 && lastLevel.length() == 1) {
            return true;
        }

        if (lastLevel.length() == curLevel.length() - 1) {
            return canReachTop(lastLevel, "", map);
        }

        int index = lastLevel.length();
        String key = curLevel.substring(index, index + 2);

        if (map.containsKey(key)) {
            for (char c : map.get(key)) {
                if (canReachTop(curLevel, lastLevel + c, map)) {
                    return true;
                }
            }
        }
        return false;
    }

}

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)