public class Solution {
    private int row;
    private int col;
    private int len;
    
    private boolean check(char[][] board, int si, int sj) {
        return (si >=0 && si < row && sj >=0 && sj < col);
    }
    
    private boolean search(char[][] board, int si, int sj, int idx, String word) {
        if (idx > len - 1) {
            return true;
        }
        if (!check(board, si, sj) || word.charAt(idx) != board[si][sj] || board[si][sj] == '.') {
            return false;
        }
        char pre = board[si][sj];
        board[si][sj] = '.'; // 用一个非字母的字符标记
        if(search(board, si - 1, sj, idx + 1, word) || search(board, si + 1, sj, idx + 1, word) || search(board, si, sj - 1, idx + 1, word) || search(board, si, sj + 1, idx + 1, word)) { // 四个方向搜索
            return true;
        }
        board[si][sj] = pre;
        return false;
    }
    
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0 || word == null || word.length() == 0) {
            return false;
        }
        row = board.length;
        col = board[0].length;
        len = word.length();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (search(board, i, j, 0, word)) {
                    return true;
                }
            }
        }
        return false;
    }
}