https://leetcode.com/problems/pyramid-transition-matrix/
BFS,把 pattern 用 map 存起来,然后 bfs 从下向上一层一层尝试每个 pattern 是否可行。注意状态的转移。
class Solution {
int N;
Map<String, List<Character>> map;
public boolean pyramidTransition(String bottom, List<String> allowed) {
N = bottom.length();
map = new HashMap<>();
for (String s : allowed) {
String k = s.substring(0, 2);
List<Character> list = map.getOrDefault(k, new ArrayList<>());
list.add(s.charAt(2));
map.put(k, list);
}
char[][] arr = new char[N][N];
for (int i = 0; i < N; i++) {
arr[N - 1][i] = bottom.charAt(i);
}
return bfs(arr, N - 1, 0);
}
public boolean bfs(char[][] arr, int i, int j) {
if (i == 0) return true;
if (j == i) return bfs(arr, i - 1, 0);
List<Character> list = map.get("" + arr[i][j] + arr[i][j + 1]);
if (list == null) return false;
for (Character c : list) {
arr[i - 1][j] = c;
if (bfs(arr, i, j + 1)) return true;
}
return false;
}
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/sinat_42483341/article/details/121629086
内容来源于网络,如有侵权,请联系作者删除!