LC79—单词搜索

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

class Solution {
   
   private static final int[][] DIR = {
   {
   -1, 0}, {
   0, -1}, {
   0, 1}, {
   1, 0}};
    private int rows;
    private int cols;
    private int len;
    private boolean[][] visied;
    private char[] charArray;
    private char[][] board;

    public boolean exist(char[][] board, String word) {
   
        rows = board.length;
        cols = board[0].length;
        if (rows == 0) {
   
            return false;
        }

        visied = new boolean[rows][cols];
        this.len = word.length();
        this.charArray = word.toCharArray();
        this.board = board;
        for (int i = 0; i < rows; i++) {
   
            for (int j = 0; j < cols; j++) {
   
                if (dfs(i, j, 0)) {
   
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int x, int y, int begin) {
   
        if (begin == len - 1) {
   
            return board[x][y] == charArray[begin];
        }
        if (board[x][y] == charArray[begin]) {
   
            visied[x][y] = true;
            for (int i = 0; i < DIR.length; i++) {
   
                int newx = x + DIR[i][0];
                int newy = y + DIR[i][1];
                if (inArea(newx, newy) && !visied[newx][newy]) {
   
                    if (dfs(newx, newy, begin + 1)) {
   
                        return true;
                    }
                }

            }
            visied[x][y] = false;
        }
        return false;
    }

    private boolean inArea(int x, int y) {
   
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
}