深度优先搜索+回溯解决网格问题

图片说明


class Solution {
    public boolean exist(char[][] board, String word) {

        char[] words = word.toCharArray();
        int[][] flag = new int[board.length][board[0].length];
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(dfs(board, i, j, words, 0, flag)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, int r, int c, char[] words, int len, int[][] flag){
        if(r < 0 || r >= board.length || c < 0 || c >= board[0].length || words[len] != board[r][c] || flag[r][c] == 1){
            return false;
        }
        //终止条件
        if(len == words.length - 1){
            return true;
        }
        //进行标记
        flag[r][c] = 1;
        //回溯
        if(dfs(board, r+1, c, words, len+1, flag) || dfs(board, r, c+1, words, len+1, flag) || dfs(board, r-1, c, words, len+1, flag) || dfs(board, r, c-1, words, len+1, flag))
            return true;
        //进行撤销
        flag[r][c] = 0;
        return false;
    }
}
字节算法题解 文章被收录于专栏

最近在刷字节的题库!! 春招给我冲!!!

全部评论

相关推荐

10-07 20:48
门头沟学院 Java
听说改名就会有offer:可能是实习上着班想到后面还要回学校给导师做牛马,看着身边都是21-25的年纪,突然emo了了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务