题目描述

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:

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

算法1

(暴力DFS枚举) O(2^n)

Java 代码

public class LeetCode756 {

    HashSet<Character>[][] allows = new HashSet[7][7];

    public boolean pyramidTransition(String bottom, List<String> allowed) {
        if (allowed.size() < 1) {
            return false;
        }

        allowed.forEach(allow -> {
            int a = allow.charAt(0) - 'A';
            int b = allow.charAt(1) - 'A';
            char c = allow.charAt(2);
            if (allows[a][b] == null) {
                allows[a][b] = new HashSet<>();
            }
            allows[a][b].add(c);
        });

        return dfs(bottom, "");
    }

    /**
     * 能否从上一层bottom是否能枚举出当前层的结果
     * @param last 上一层
     * @param now  当前层
     * @return
     */
    private boolean dfs(String last, String now) {
        // 上一层就是顶点了
        if (last.length() == 1) {
            return true;
        }

        // 说明当前这层枚举完毕。递归做更上一层的dfs任务
        if (now.length() + 1 == last.length()) {
            return dfs(now, "");
        }

        // Input: bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
        // 枚举allows   (aloows是allowed从一维转二维后的视图)
        // candidate = G, E, A, F
        int a = last.charAt(now.length()) - 'A';
        int b = last.charAt(now.length() + 1) - 'A';
        if (null == allows[a][b]) {
            return false;
        }
        for (char candidate : allows[a][b]) {
            if (dfs(last, now + candidate)) {
                return true;
            }
        }
        return false;
    }

}