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;
	}
}