二维递归 79. Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,

Given board =

[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

public class Solution79 {

    public boolean exist(char[][] board, String word) {
        int[][] flag=new int[board.length][board[0].length]; //给每个flag标志，如果没有访问就标注0
        for (int i = 0; i < flag.length; i++) {
            for (int j = 0; j < flag[0].length; j++) {
                flag[i][j]=0;
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {  //可以重任意一个点开始访问
                if (helper(board,i,j,flag,word,0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean helper(char[][] board, int i, int j, int[][] flag, String word, int k) {
        if (i<0||j<0||i>=board.length||j>=board[0].length||flag[i][j]==1) {
            return false; //如果访问了或者越界返回false
        }
        if (k<word.length()&&board[i][j]!=word.toCharArray()[k]) {
            return false;//如果有一个字符不同就返回false
        }
        if (k==word.length()-1) {//
            return true;
        }
        flag[i][j]=1;//访问一次就标记
        if(helper(board, i+1, j, flag, word, k+1)||
        helper(board, i, j+1, flag, word, k+1)||
        helper(board, i-1, j, flag, word, k+1)||
        helper(board, i, j-1, flag, word,k+1)){
            return true;
        }
        flag[i][j]=0;//返回要去掉标记
        return false;
    }


    public static void main(String[] args) {
        char[][] board={{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word="ABCCED";
        boolean f=new Solution79().exist(board, word);
        System.out.println(f);
    }

}