79.单词搜索

 递归调用判断
 boolean类型的二维数组用于判断当前字母是否已使用过  
 int[][] directions = {{0,-1},{0,1},{1,0},{-1,0}}; 用于处理边界问题   

class Solution {
    public boolean exist(char[][] board, String word) {
        boolean result = false;
        int y = board.length, x = board[0].length;
        boolean visited[][] = new boolean[y][x];
        for(int Y = 0; Y<y; Y++){
            for(int X = 0; X<x; X++){
                if(board[Y][X] == word.charAt(0)){
                    boolean flag = check(board, Y, X, visited, word, 0);
                    if(flag){
                        return true;
                    }
                }
            }
        }
        return result;
    }

    public boolean check(char[][] board, int Y, int X, boolean[][] visited, String word, int k){
        boolean checkResult = false;
        if(board[Y][X] != word.charAt(k)){
            return false;
        }else if(k == word.length()-1){
            return true;
        }

        visited[Y][X] = true;
        int[][] directions = {{0,-1},{0,1},{1,0},{-1,0}};
        for(int[] dir: directions){
            int newY = Y + dir[0], newX = X + dir[1];
            if(newY >= 0 && newY < board.length && newX >= 0 && newX < board[0].length){
                if(!visited[newY][newX]){
                    boolean flag = check(board, newY, newX, visited, word, k+1);
                    if(flag){
                        checkResult = true;
                        break;
                    }
                }

            }
        }
        visited[Y][X] = false;  //每次递归调用完后为保证外层方法正确性，要复原本次的修改
        return checkResult;  

    }
}