欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

79. Word Search

程序员文章站 2022-07-14 17:30:09
...

Medium

看的答案,这种简单粗暴的DFS还是不会写. 抄过来又觉得很简单,多写几道多体会体会吧

class Solution {
    //DFS
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];        
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (board[i][j] == word.charAt(0) && dfsHelper(board, word, i, j, 0, visited)){
                    return true;
                }        
            }
        } 
        return false;
    }
    
    private boolean dfsHelper(char[][] board, String word, int i, int j, int index, boolean[][] visited){
        if (index == word.length()){
            return true;
        }        
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(index)){
            return false;
        }
        visited[i][j] = true;
        if (dfsHelper(board, word, i + 1, j, index + 1, visited) || dfsHelper(board, word, i - 1, j, index + 1, visited) ||
           dfsHelper(board, word, i, j + 1, index + 1, visited) || dfsHelper(board, word, i, j - 1, index + 1, visited)){
            return true;
        }
        visited[i][j] = false;
        return false;
    }
}