Joey LIU | NANTSOU


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public boolean exist(char[][] board, String word) {
        char[] chars = word.toCharArray();
        int m = board.length, n = board[0].length;
        boolean[][] chk = new boolean[m][n];

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (dfs(board, chars, chk, r, c, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, char[] chars, boolean[][] chk, int r, int c, int idx) {
        if (idx == chars.length - 1 && board[r][c] == chars[idx]) {
            return true;
        } else if (board[r][c] != chars[idx]) {
            return false;
        } else {
            chk[r][c] = true;
            for (int[] dir : new int[][]{new int[]{0, 1}, new int[]{0, -1}, new int[]{1, 0}, new int[]{-1, 0}}) {
                int rn = r + dir[0], cn = c + dir[1];
                if (rn < 0 || rn >= board.length || cn < 0 || cn >= board[0].length || chk[rn][cn]) {
                    continue;
                }
                if (dfs(board, chars, chk, rn, cn, idx + 1)) {
                    return true;
                }
            }
            chk[r][c] = false;
            return false;
        }
    }
}