leetcode 756. Pyramid Transition Matrix | 756. 金字塔转换矩阵(BFS)

x33g5p2x  于2021-11-30 转载在 其他  
字(0.8k)|赞(0)|评价(0)|浏览(155)

题目

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

相关文章

微信公众号

最新文章

更多