单词搜索

题目：
给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

代码：

class Solution {
    public boolean exist(char[][] board, String word) {
        boolean res = false;
        int m = board.length;
        int n = board[0].length;
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                int[][] flag = new int[m][n];
                res |= fExist(board,flag,word,0,i,j);
            }
        }
        return res;
    }
    
    private boolean fExist(char[][] board,int[][] flag,String word,int index,int i,int j) {
        if(index > word.length()-1) {
            return true;
        }
        if(i<0 || i>board.length-1 || j<0 || j>board[0].length-1) {
            return false;
        }
        if(board[i][j]==word.charAt(index) && flag[i][j]==0) {
            flag[i][j] = 1;
            boolean res = fExist(board,flag,word,index+1,i+1,j) || fExist(board,flag,word,index+1,i-1,j)
                || fExist(board,flag,word,index+1,i,j-1) || fExist(board,flag,word,index+1,i,j+1);
           // 记得释放回原状态
            flag[i][j] = 0;
            return res;
        }else {
            return false;
        }
    }
}