题目

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;
    }
}