79. 单词搜索

class Solution {
    int n;
    int m;
    int dx[] = new int[] { -1, 0, 1, 0 };
    int dy[] = new int[] { 0, -1, 0, 1 };
    public boolean exist(char[][] board, String word) {
        if(board.length==0||board[0].length==0)return false;
        n = board.length;
        m = board[0].length;
        for (int i = 0; i < n; i++) {
            for (int x = 0; x < m; x++) {
                if (dfs(word, board,i, x,0))
                    return true;
            }
        }
        return false;
    }
    private boolean dfs(String word, char[][] board, int i, int x,int u) {
        if(board[i][x]!=word.charAt(u))return false;                                            //省去一个变量来保存状态
        if(u == word.length()-1) return true;

        board[i][x] = '.';                                                                                //替换 这个是一个重要思想       省去一个往回走的判断数组
        for(int z = 0 ; z < 4 ; z++) {
            if (i+dx[z] >= 0 && x+dy[z] >= 0&& i+dx[z] < n && x+dy[z] < m) 
                if(dfs(word , board , i+dx[z],x+dy[z],u+1))
                    return true;
        }
        board[i][x] = word.charAt(u);                                                //还原 真的赞

        return false;
    }
}