756. Pyramid Transition Matrix

756. Pyramid Transition Matrix

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 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 = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]Output: trueExplanation:We can stack the pyramid like this: A / \ D E / \ / \X Y ZThis 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: falseExplanation:We can't stack the pyramid to the

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’}.

Intuition

We exhaustively try every combination of blocks.

Algorithm

We can work in either strings or integers, but we need to create a transition map T from the list of allowed triples. This map T[x][y] = {set of z} will be all possible parent blocks for a left child of x and a right child of y. When we work in strings, we use Set, and when we work in integers, we will use the set bits of the result integer.

Afterwards, to solve a row, we generate every possible combination of the next row and solve them. If any of those new rows are solvable, we return True, otherwise False.

We can also cache intermediate results, saving us time. This is illustrated in the comments for Python. For Java, all caching is done with lines of code that mention the integer R.

class Solution { int[][] T; Set seen; public boolean pyramidTransition(String bottom, List allowed) { T = new int[7][7]; for (String a: allowed) T[a.charAt(0) - 'A'][a.charAt(1) - 'A'] |= 1 << (a.charAt(2) - 'A'); seen = new HashSet(); int N = bottom.length(); int[][] A = new int[N][N]; int t = 0; for (char c: bottom.toCharArray()) A[N-1][t++] = c - 'A'; return solve(A, 0, N-1, 0); } public boolean solve(int[][] A, long R, int N, int i) { if (N == 1 && i == 1) { // If successfully placed entire pyramid return true; } else if (i == N) { if (seen.contains(R)) return false; // If we've already tried this row, give up seen.add(R); // Add row to cache return solve(A, 0, N-1, 0); // Calculate next row } else { int w = T[ A[N][i] ][ A[N][i+1] ]; for (int b = 0; b < 7; ++b) { if (((w >> b) & 1) != 0) { A[N-1][i] = b; if (solve(A, R * 8 + (b+1), N, i+1)) return true; } } return false; } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。