Skip to content

Commit a69f22c

Browse files
fishercoder1534fishercoder1534
committed
add 756
1 parent 969aab6 commit a69f22c

File tree

3 files changed

+129
-0
lines changed

3 files changed

+129
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@ Your ideas/fixes/algorithms are more than welcome!
2626
|763|[Partition Labels](https://leetcode.com/problems/partition-labels/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_763.java) | O(n) | O(1) | |Medium|
2727
|762|[Prime Number of Set Bits in Binary Representation](https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_762.java) | O(n) | O(1) | |Easy|
2828
|760|[Find Anagram Mappings](https://leetcode.com/problems/find-anagram-mappings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_760.java) | O(n^2) | O(1) | |Easy|
29+
|756|[Pyramid Transition Matrix](https://leetcode.com/problems/pyramid-transition-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_756.java) | O(?) | O(?) | |Medium| Backtracking
2930
|755|[Pour Water](https://leetcode.com/problems/pour-water/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_755.java) | O(V*N) | O(1) | |Medium| Array
3031
|754|[Reach a Number](https://leetcode.com/problems/reach-a-number/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_754.java) | O(n) | O(1) | |Medium| Math
3132
|750|[Number Of Corner Rectangles](https://leetcode.com/problems/number-of-corner-rectangles/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_750.java) | O((m*n)^2) | O(1) | |Medium|

‎src/main/java/com/fishercoder/solutions/_756.java

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.ArrayList;
4+
import java.util.HashMap;
5+
import java.util.List;
6+
import java.util.Map;
7+
8+
/**
9+
* 756. Pyramid Transition Matrix
10+
*
11+
* We are stacking blocks to form a pyramid. Each block has a color which is a one letter string, like `'Z'`.
12+
* For every block of color `C` we place not in the bottom row,
13+
* we are placing it on top of a left block of color `A` and right block of color `B`.
14+
* We are allowed to place the block there only if `(A, B, C)` is an allowed triple.
15+
* We start with a bottom row of bottom,
16+
* represented as a single string. We also start with a list of allowed triples allowed.
17+
* Each allowed triple is represented as a string of length 3.
18+
* Return true if we can build the pyramid all the way to the top, otherwise false.
19+
20+
Example 1:
21+
Input: bottom = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]
22+
Output: true
23+
Explanation:
24+
We can stack the pyramid like this:
25+
A
26+
/ \
27+
D E
28+
/ \ / \
29+
X Y Z
30+
31+
This works because ('X', 'Y', 'D'), ('Y', 'Z', 'E'), and ('D', 'E', 'A') are allowed triples.
32+
33+
Example 2:
34+
Input: bottom = "XXYX", allowed = ["XXX", "XXY", "XYX", "XYY", "YXZ"]
35+
Output: false
36+
Explanation:
37+
We can't stack the pyramid to the top.
38+
Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.
39+
40+
Note:
41+
bottom will be a string with length in range [2, 8].
42+
allowed will have length in range [0, 200].
43+
Letters in all strings will be chosen from the set {'A', 'B', 'C', 'D', 'E', 'F', 'G'}.
44+
*/
45+
public class _756 {
46+
public static class Solution1 {
47+
/**credit: https://discuss.leetcode.com/topic/116042/java-solution-map-backtracking*/
48+
public boolean pyramidTransition(String bottom, List<String> allowed) {
49+
Map<String, List<String>> map = new HashMap<>();
50+
for (String s : allowed) {
51+
String key = s.substring(0, 2);
52+
if (!map.containsKey(key)) {
53+
map.put(key, new ArrayList<>());
54+
}
55+
map.get(key).add(s.substring(2));
56+
}
57+
58+
return helper(bottom, map);
59+
}
60+
61+
private boolean helper(String bottom, Map<String, List<String>> map) {
62+
if (bottom.length() == 1) return true;
63+
for (int i = 0; i < bottom.length() - 1; i++) {
64+
if (!map.containsKey(bottom.substring(i, i + 2))) {
65+
return false;
66+
}
67+
}
68+
List<String> ls = new ArrayList<>();
69+
getList(bottom, 0, new StringBuilder(), ls, map);
70+
for (String s : ls) {
71+
if (helper(s, map)) {
72+
return true;
73+
}
74+
}
75+
return false;
76+
}
77+
78+
private void getList(String bottom, int idx, StringBuilder sb, List<String> ls,
79+
Map<String, List<String>> map) {
80+
if (idx == bottom.length() - 1) {
81+
ls.add(sb.toString());
82+
return;
83+
}
84+
for (String s : map.get(bottom.substring(idx, idx + 2))) {
85+
sb.append(s);
86+
getList(bottom, idx + 1, sb, ls, map);
87+
sb.deleteCharAt(sb.length() - 1);
88+
}
89+
}
90+
}
91+
}

‎src/test/java/com/fishercoder/_756Test.java

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._756;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
import org.junit.BeforeClass;
7+
import org.junit.Test;
8+
9+
import static org.junit.Assert.assertEquals;
10+
11+
public class _756Test {
12+
private static _756.Solution1 solution1;
13+
private static List<String> allowed;
14+
15+
@BeforeClass
16+
public static void setup() {
17+
solution1 = new _756.Solution1();
18+
}
19+
20+
@Test
21+
public void test1() {
22+
allowed = Arrays.asList("XYD", "YZE", "DEA", "FFF");
23+
assertEquals(true, solution1.pyramidTransition("XYZ", allowed));
24+
}
25+
26+
@Test
27+
public void test2() {
28+
allowed = Arrays.asList("XXX", "XXY", "XYX", "XYY", "YXZ");
29+
assertEquals(false, solution1.pyramidTransition("XXYX", allowed));
30+
}
31+
32+
@Test
33+
public void test3() {
34+
allowed = Arrays.asList("BCE", "BCF", "ABA", "CDA", "AEG", "FAG", "GGG");
35+
assertEquals(false, solution1.pyramidTransition("ABCD", allowed));
36+
}
37+
}

0 commit comments

Comments
 (0)