Related:
String pyramids transition matrix - Airbnb
https://leetcode.com/problems/pyramid-transition-matrix/
这道题首先我们第一反应是考虑BFS或者DFS，但仔细考虑过后BFS事实上是做不了的，比如对于ABC和{ABD, ABE, BCK}，在AB的时候我们有两种选择，而我们BFS只能取一个。所以我们需要用DFS来遍历所有的可能，从最底层开始直到最顶层。对于每个合法的block，我们可以用bit来存，因为只会用到7个字符，比如我们用map[a][c]表示AC后面能够接的字符，每一位代表从a到g的每个字符。时间复杂度O(N^k)，N为最底层的长度，k为所用的字符数量
X. Multiple phrases DFS
https://leetcode.com/problems/pyramid-transition-matrix/discuss/113054/Java-solution-map-%2B-backtracking
X. Backtrack + DFS + Cache
https://leetcode.com/problems/pyramid-transition-matrix/discuss/113062/C%2B%2B-passed-counter-example-DFS-with-memoization-6-ms
X. https://leetcode.com/problems/pyramid-transition-matrix/discuss/170870/concise-C%2B%2B-recursive-solution-(10-line)
X. DP - Wrong
Approach #1: State to State Transition [Wrong Answer]
https://leetcode.com/problems/pyramid-transition-matrix/discuss/113037/counter-example-to-the-standard-code
For the following example:
"ABCD"
["BCE","BCF","ABA","CDA","AEG","FAG","GGG"]
Should we output false (if I am interpreting the problem correctly)?
But the standard code outputs true. Could anyone explain this?
Since the DP method considered the characters independent from the lower layer. A character can be used only if it's based on certain character pairs, however in the DP method if a character can be used based on a pair, it will be marked as
注意allowed中的三元组是可以重复利用的，这样我们定义dp：
dp[i][j][k]: 表示第i层上，第j个元素为k
1
根据bottom，可以初始化每个位置j上含有的字符bottom[j]， dp更新式如下：
dp[i][j][k] = true if dp[i + 1][j][l] = true && dp[i + 1][j + 1][r] = true && lrk组成的字符串在allowed中出现过。
String pyramids transition matrix - Airbnb
https://leetcode.com/problems/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: 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:
bottomwill be a string with length in range[2, 8].allowedwill have length in range[0, 200].- Letters in all strings will be chosen from the set
{'A', 'B', 'C', 'D', 'E', 'F', 'G'}
这道题让我们累一个金字塔，用字母来代表每块砖的颜色，给了一个allowed数组，里面都是长度为三的字符串，比如“ABC”表示C可以放在A和B的上方，注意AB上面也可以放其他的，比如“ABD”也可以同时出现，不过搭积木的时候只能选择一种。给了我们一个bottom字符串，是金字塔的底层，问我们能不能搭出一个完整的金字塔。那么实际上我们就是从底层开始，一层一层的向上来累加，直到搭出整个金字塔。我们先来看递归的解法，首先由于我们想快速知道两个字母上方可以放的字母，需要建立基座字符串和上方字符集合之间的映射，由于上方字符可以不唯一，所以用个HashSet来放字符。我们的递归函数有三个参数，当前层字符串cur，上层字符串above，还有我们的HashMap。如果cur的大小为2，above的大小为1，那么说明当前已经达到金字塔的顶端了，已经搭出来了，直接返回true。否则看，如果上一层的长度比当前层的长度正好小一个，说明上一层也搭好了，我们现在去搭上上层，于是调用递归函数，将above当作当前层，空字符串为上一层，将调用的递归函数结果直接返回。否则表示我们还需要继续去搭above层，我们先算出above层的长度pos，然后从当前层的pos位置开始取两个字符，就是above层接下来需要搭的字符的基座字符，举个例子如下：
D / \ / \ A B C
我们看到现在above层只有一个D，那么pos为1，在cur层1位置开始取两个字符，得到"BC"，即是D的下一个位置的字符的基座字符串base。取出了base后，如果HashMap中有映射，则我们遍历其映射的字符集合中的所有字符，对每个字符都调用递归函数，此时above字符串需要加上这个遍历到的字符，因为我们在尝试填充这个位置，如果有返回true的，那么当前递归函数就返回true了，否则最终返回false.
我们在每层字符串作为底座的基础上，向上面建立新的一层。所以是个递归过程。建立的方式是通过允许的组合，这个组合是我们可以通过下面的这两块砖来获得上面可以累加什么砖的方式。
所以，用curr表示当前层，用above表示上层。当curr大小为2，above为1，那么金字塔完成。如果curr = above + 1，说明上面这层已经弄好了，下面使用above来作为当前层，继续递归。
如果上面两个都不满足，说明需要继续堆积above，做的方式是在应该继续堆积的位置上，找出能堆积哪些字符，并把这个字符堆积上去，做递归。
bool pyramidTransition(string bottom, vector<string>& allowed) { unordered_map<string, unordered_set<char>> m; for (string str : allowed) { m[str.substr(0, 2)].insert(str[2]); } return helper(bottom, "", m); } bool helper(string cur, string above, unordered_map<string, unordered_set<char>>& m) { if (cur.size() == 2 && above.size() == 1) return true; if (above.size() == cur.size() - 1) return helper(above, "", m); int pos = above.size(); string base = cur.substr(pos, 2); if (m.count(base)) { for (char ch : m[base]) { if (helper(cur, above + string(1, ch), m)) { return true; } } } return false; }
https://www.acwing.com/solution/leetcode/content/189/
https://my.oschina.net/liyurong/blog/1616709
public boolean pyramidTransition(String bottom, List<String> allowed) {
Map<String,List<String>> map = new HashMap<>();//键为左右节点字符串，值为根节点的集合
for (String str : allowed){
String key = str.substring(0,2);
if (! map.containsKey(key)){
map.put(key,new ArrayList<>());
}
map.get(key).add(str.substring(2));
}
return dfs(map,bottom,new StringBuilder(),0);
}
public boolean dfs(Map<String,List<String>> map,String bottom,StringBuilder nextBottom,int p){
if (p == bottom.length() - 1){//完成一行，更新bottom和p
bottom = nextBottom.toString();
nextBottom = new StringBuilder();
p = 0;
}
if (bottom.length() == 1) return true;
String key = bottom.substring(p,p + 2);
if (map.containsKey(key)){
for (String val : map.get(key)){
nextBottom.append(val);
if (dfs(map,bottom,nextBottom,p + 1)) return true;
nextBottom.setLength(nextBottom.length() - 1);//还原
}
}
return false;
}
http://hehejun.blogspot.com/2018/10/leetcodepyramid-transition-matrix.htmlhttps://my.oschina.net/liyurong/blog/1616709
public boolean pyramidTransition(String bottom, List<String> allowed) {
Map<String,List<String>> map = new HashMap<>();//键为左右节点字符串，值为根节点的集合
for (String str : allowed){
String key = str.substring(0,2);
if (! map.containsKey(key)){
map.put(key,new ArrayList<>());
}
map.get(key).add(str.substring(2));
}
return dfs(map,bottom,new StringBuilder(),0);
}
public boolean dfs(Map<String,List<String>> map,String bottom,StringBuilder nextBottom,int p){
if (p == bottom.length() - 1){//完成一行，更新bottom和p
bottom = nextBottom.toString();
nextBottom = new StringBuilder();
p = 0;
}
if (bottom.length() == 1) return true;
String key = bottom.substring(p,p + 2);
if (map.containsKey(key)){
for (String val : map.get(key)){
nextBottom.append(val);
if (dfs(map,bottom,nextBottom,p + 1)) return true;
nextBottom.setLength(nextBottom.length() - 1);//还原
}
}
return false;
}
这道题首先我们第一反应是考虑BFS或者DFS，但仔细考虑过后BFS事实上是做不了的，比如对于ABC和{ABD, ABE, BCK}，在AB的时候我们有两种选择，而我们BFS只能取一个。所以我们需要用DFS来遍历所有的可能，从最底层开始直到最顶层。对于每个合法的block，我们可以用bit来存，因为只会用到7个字符，比如我们用map[a][c]表示AC后面能够接的字符，每一位代表从a到g的每个字符。时间复杂度O(N^k)，N为最底层的长度，k为所用的字符数量
bool pyramidTransition(string bottom, vector<string>& allowed) {
int len = bottom.size();
vector<vector<int>> pyramid(8, vector<int>(8, 0)), map(7, vector<int>(7, 0));
for (auto& str : allowed)
map[str[0] - 'A'][str[1] - 'A'] |= 1 << (str[2] - 'A');
for (int i = 0; i < bottom.size(); ++i)pyramid[len - 1][i] = bottom[i] - 'A';
return dfs(pyramid, map, len - 1, 0);
}
private:
//N length of current row
//i index of current column
bool dfs(vector<vector<int>>& pyramid, vector<vector<int>>& map, int N, int i)
{
if (N == 1 && i == 1)return true;
if (i == N)return dfs(pyramid, map, N - 1, 0);
int bit = map[pyramid[N][i]][pyramid[N][i + 1]];
for (int j = 0; j < 7; ++j)
{
if (bit & (1 << j))
{
pyramid[N - 1][i] = j;
if (dfs(pyramid, map, N, i + 1))
return true;
}
}
return false;
}
https://leetcode.com/problems/pyramid-transition-matrix/discuss/113054/Java-solution-map-%2B-backtracking
public boolean pyramidTransition(String bottom, List<String> allowed) {
Map<String, List<String>> map = new HashMap<>();
for (String s : allowed) {
String key = s.substring(0,2);
if (!map.containsKey(key)) map.put(key, new ArrayList<String>());
map.get(key).add(s.substring(2));
}
return helper(bottom, map);
}
private boolean helper(String bottom, Map<String, List<String>> map) {
if(bottom.length() == 1) return true;
for (int i = 0; i<bottom.length()-1; i++) {
if (!map.containsKey(bottom.substring(i,i+2))) return false;
}
List<String> ls = new ArrayList<>();
getList(bottom, 0, new StringBuilder(), ls, map);
for (String s : ls) {
if (helper(s, map)) return true;
}
return false;
}
private void getList(String bottom, int idx, StringBuilder sb, List<String> ls, Map<String, List<String>> map) {
if (idx == bottom.length() - 1) {
ls.add(sb.toString());
return;
}
for (String s : map.get(bottom.substring(idx, idx+2))) {
sb.append(s);
getList(bottom, idx + 1, sb, ls, map);
sb.deleteCharAt(sb.length()-1);
}
}X. Backtrack + DFS + Cache
https://leetcode.com/problems/pyramid-transition-matrix/discuss/113062/C%2B%2B-passed-counter-example-DFS-with-memoization-6-ms
Theoretically, BFS should work. We can use unordered_set to keep all possible strings for each level. Then move up and generate possible combinations for next level. When reaching the top, if the set is non-empty, return true. However, it will result in TLE. The advantage of DFS is early termination. Once we find a valid solution, we don't have to traverse the whole tree, although the worse case runtime is the same.
A couple optimization:
- memoization: unordered_set invalid, to keep all the strings that won't work.
- 2D vector to keep edges, such as "ABE".
- early termination if a string cannot generate a string of next level. For example, "ABFE" while there is no edge of "BF#".
private Map<Character, Map<Character, List<Character>>> map = new HashMap<>();
private Map<String, Boolean> memo = new HashMap<>();
// is it possible to build a pyramid upon "bottom"?
private boolean dfs1(String bottom) {
if (bottom.length() == 1) {
return true;
}
if (memo.get(bottom) != null) {
return memo.get(bottom);
}
boolean res = dfs2(bottom, new StringBuilder(), 0);
memo.put(bottom, res);
return res;
}
// is it possible to build a pyramid upon "bottom"
// given the first |next| elements has been fixed in ceiling
private boolean dfs2(String bottom, StringBuilder ceiling, int next) {
if (next == bottom.length() - 1) {
return dfs1(ceiling.toString());
}
// consider the next element in ceiling
if (map.get(bottom.charAt(next)) == null) {
return false;
}
if (map.get(bottom.charAt(next)).get(bottom.charAt(next+1)) == null) {
return false;
}
for (char ch : map.get(bottom.charAt(next)).get(bottom.charAt(next+1))) {
ceiling.append(ch);
if (dfs2(bottom, ceiling, next+1)) {
return true;
}
ceiling.deleteCharAt(ceiling.length() - 1);
}
return false;
}
public boolean pyramidTransition(String bottom, List<String> allowed) {
for (String edge : allowed) {
char a = edge.charAt(0);
char b = edge.charAt(1);
char c = edge.charAt(2);
map.putIfAbsent(a, new HashMap<>());
map.get(a).putIfAbsent(b, new ArrayList<>());
map.get(a).get(b).add(c);
}
return dfs1(bottom);
}X. https://leetcode.com/problems/pyramid-transition-matrix/discuss/170870/concise-C%2B%2B-recursive-solution-(10-line)
Dealing with layer is a little bit awkward, here I use a space character to separate the layer and then it turns to a simple string.
public boolean pyramidTransition(String bottom, List<String> allowed) {
Map<String, List<Character>> map = new HashMap<>();
for (String a : allowed) {
String b = a.substring(0, 2);
if (!map.containsKey(b)) map.put(b, new ArrayList<>());
map.get(b).add(a.charAt(2));
}
return canStack(bottom + ' ', map);
}
boolean canStack(String s, Map<String, List<Character>> map) {
if (s.length() == 1) return true;
String b = s.substring(0, 2);
if (b.charAt(1) == ' ') return canStack(s.substring(2, s.length()) + ' ', map);
for (Character c : map.getOrDefault(b, new ArrayList<>())) {
if (canStack(s.substring(1, s.length()) + c, map)) return true;
}
return false;
} public boolean pyramidTransition(String bottom, List<String> allowed) {
Map<String, List<String>> map = new HashMap<>();
for (String s : allowed) {
String key = s.substring(0,2);
if (!map.containsKey(key)) map.put(key, new ArrayList<String>());
map.get(key).add(s.substring(2));
}
return helper(bottom, map);
}
private boolean helper(String bottom, Map<String, List<String>> map) {
if(bottom.length() == 1) return true;
for (int i = 0; i<bottom.length()-1; i++) { //首先判断上一层无法构建的情况，如果无法构建直接return false
if (!map.containsKey(bottom.substring(i,i+2))) return false;
}
List<String> ls = new ArrayList<>();//使用dfs的方式找到上一层所有可能结果
getList(bottom, 0, new StringBuilder(), ls, map);
for (String s : ls) {//遍历所有结果进行递归搜索
if (helper(s, map)) return true;
}
return false;
}
// dfs的方式找到所有可能的上一层的结果
// 结果存储到 candidates 数组中
// cur 存储当前dfs的进度
private void getList(String bottom, int idx, StringBuilder sb, List<String> ls, Map<String, List<String>> map) {
if (idx == bottom.length() - 1) {
ls.add(sb.toString());
return;
}
for (String s : map.get(bottom.substring(idx, idx+2))) {
sb.append(s);
getList(bottom, idx + 1, sb, ls, map);
sb.deleteCharAt(sb.length()-1);
}
}
Approach #1: State to State Transition [Wrong Answer]
Intuition and Algorithm
We model the states that blocks can be in. Each state is a binary number where the
kth bit is set if the kth type of block is a possibility. Then, we create a transition map T[state1][state2] -> state that takes a left state and a right state and outputs all possible parent states.
At the end, applying these transitions is straightforward. However, this approach is not correct, because the transitions are not independent. If for example we have states in a row
A, {B or C}, A, and allowed triples (A, B, D), (C, A, D), then regardless of the choice of {B or C} we cannot create the next row of the pyramid.
public boolean pyramidTransition(String bottom, List<String> allowed) {
int[][] T = new int[1 << 7][1 << 7];
for (String triple : allowed) {
int u = 1 << (triple.charAt(0) - 'A');
int v = 1 << (triple.charAt(1) - 'A');
int w = 1 << (triple.charAt(2) - 'A');
for (int b1 = 0; b1 < (1 << 7); ++b1)
if ((u & b1) > 0)
for (int b2 = 0; b2 < (1 << 7); ++b2)
if ((v & b2) > 0)
T[b1][b2] |= w;
}
int[] state = new int[bottom.length()];
int t = 0;
for (char c : bottom.toCharArray())
state[t++] = 1 << (c - 'A');
while (t-- > 1)
for (int i = 0; i < t; ++i)
state[i] = T[state[i]][state[i + 1]];
return state[0] > 0;
}
For the following example:
"ABCD"
["BCE","BCF","ABA","CDA","AEG","FAG","GGG"]
Should we output false (if I am interpreting the problem correctly)?
But the standard code outputs true. Could anyone explain this?
Since the DP method considered the characters independent from the lower layer. A character can be used only if it's based on certain character pairs, however in the DP method if a character can be used based on a pair, it will be marked as
true, and it will be used for other pairs even if it's not allowed
这是一种DP的解法，建立一个三维的dp数组，其中dp[i][j][ch]表示在金字塔(i, j)位置上是否可以放字符ch，金字塔的宽和高已经确定了，都是n。每个位置对应着nxn的数组的左半边，如下所示：
F _ _
D E _
A B C
D E _
A B C
除了底层，每个位置可能可以放多个字符，所以这里dp数组是一个三维数组，第三维的长度为7，因为题目中限定了字母只有A到G共7个，如果dp值为true，表示该位置放该字母，我们根据bottom字符串来初始化dp数组的底层。这里还是需要一个HashMap，不过跟上面的解法略有不同的是，我们建立上方字母跟其能放的基座字符串集合的映射，因为一个字母可能可以放多个位置，所以用个集合来表示。然后我们就开始从倒数第二层开始往顶部更新啦，对于金字塔的每个位置，我们都遍历A到G中所有的字母，如果当前字母在HashMap中有映射，则我们遍历对应的基座字符串集合中的所有字符串，基座字符串共有两个字母，左边的字母对应的金字塔中的位置是(i + 1, j)，右边的字母对应的位置是(i + 1, j + 1)，我们只要在这两个位置上分别查询对应的字母的dp值是否为true，是的话，说明当前位置有字母可以放，我们将当前位置的字母对应的dp值赋值为true。这样，当我们整个更新完成了之后，我们只要看金字塔顶端位置(0, 0)是否有字母可以放，有的话，说明可以搭出金字塔，返回true，否则返回false
https://leetcode.com/problems/pyramid-transition-matrix/discuss/113075/DP-O(n2-*-m)
n is the size of bottom, m is the length of allowed.
Update: even this solution is ACed, personally, I don't think it is correct - see https://discuss.leetcode.com/topic/115541/counter-example-to-the-standard-code
But, I still think it's worth to note it down here to help understand what the official solution wanted it be.
public boolean pyramidTransition(String bottom, List<String> allowed) {
int n = bottom.length();
Map<Character, List<String>> map = new HashMap<>();
for(String s : allowed) {
char key = s.charAt(2);
if (!map.containsKey(key))
map.put(key, new ArrayList<>());
map.get(key).add(s.substring(0,2));
}
boolean[][][] dp = new boolean[n][n][7];
for(int i = 0; i < n; i++) {
dp[n-1][i][bottom.charAt(i)-'A'] = true;
}
for(int i = n-2; i >= 0; i--) {
for(int j = 0; j <= i; j++)
for(char ch = 'A'; ch <= 'G'; ch++) {
if (!map.containsKey(ch)) continue;
for(String b : map.get(ch)) {
if (dp[i+1][j][b.charAt(0) - 'A'] && dp[i+1][j+1][b.charAt(1)-'A'])
dp[i][j][ch - 'A'] = true;
}
}
}
for(int i = 0; i < 7; i++)
if (dp[0][0][i]) return true;
return false;
}注意allowed中的三元组是可以重复利用的，这样我们定义dp：
dp[i][j][k]: 表示第i层上，第j个元素为k
1
根据bottom，可以初始化每个位置j上含有的字符bottom[j]， dp更新式如下：
dp[i][j][k] = true if dp[i + 1][j][l] = true && dp[i + 1][j + 1][r] = true && lrk组成的字符串在allowed中出现过。
public boolean pyramidTransition(String bottom, List<String> allowed) {
Map<String, List<String>> mem = new HashMap<>();
boolean[][] dp = new boolean[20][7];
int n = bottom.length();
for (String allow : allowed) {
mem.computeIfAbsent(allow.substring(0, 2), k -> new ArrayList<>()).add(allow.substring(2));
}
for (int i = 0; i < n; ++i) {
dp[i][bottom.charAt(i) - 'A'] = true;
}
for (int i = n - 1; i >= 1; --i) {
boolean[][] ndp = new boolean[20][7];
for (int j = 0; j < i; ++j) {
for (int l = 0; l < 7; ++l) {
for (int r = 0; r < 7; ++r) {
if (dp[j][l] && dp[j + 1][r]) {
if (mem.containsKey((char) (l + 'A') + "" + (char) (r + 'A'))) {
for (String s : mem.get((char) (l + 'A') + "" + (char) (r + 'A'))) {
ndp[j][s.charAt(0) - 'A'] = true;
}
}
}
}
}
}
dp = ndp;
}
for (int i = 0; i < 7; ++i) {
if (dp[0][i])
return true;
}
return false;
}
