给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 给定 word = "ABCCED", 返回 true. 给定 word = "SEE", 返回 true. 给定 word = "ABCB", 返回 false.思路：类似于DFS，循环二维数组board找到一个字母board[i][j]与word的首字母相同，然后以board[i][j]为起点递归进行深度遍历
class Solution { public boolean exist(char[][] board, String word) { if(word.length() <= 0) return true; for(int i=0;i<board.length;i++) for(int j=0;j<board[0].length;j++){ //flag数组用于记录网格中的字母是否已经被使用过了，防止重复使用 boolean[][] flag = new boolean[board.length][board[0].length]; boolean b = exist1(board,word,i,j,flag); if(b) return true; } return false; } //递归判断网格中是否存在word public boolean exist1(char[][] board,String word,int i,int j,boolean[][] flag){ int row = board.length; int col = board[0].length; if(flag[i][j] == true) return false; if(word.length() == 1 && word.charAt(0) == board[i][j]) return true; if(board[i][j] != word.charAt(0)) return false; else{ flag[i][j] = true; boolean b1 = false; boolean b2 = false; boolean b3 = false; boolean b4 = false; if(i > 0) b1 = exist1(board,word.substring(1),i-1,j,cloneArr(flag)); if(i < row-1) b2 = exist1(board,word.substring(1),i+1,j,cloneArr(flag)); if(j > 0) b3 = exist1(board,word.substring(1),i,j-1,cloneArr(flag)); if(j < col-1) b4 = exist1(board,word.substring(1),i,j+1,cloneArr(flag)); return (b1 || b2 || b3 || b4); } } //二维数组深度拷贝 public boolean[][] cloneArr(boolean[][] arr){ boolean[][] b = new boolean[arr.length][arr[0].length]; for(int i=0;i<arr.length;i++){ b[i] = arr[i].clone(); } return b; } }存在的问题：
可优化点：上面题解使用了flag数组记录元素是否已经被使用过了，如何做到不使用额外的数组。
思路：注意到我们使用了递归，可以做到在原数组上进行重复利用的。
class Solution { public boolean exist(char[][] board, String word) { if(word.length() <= 0) return true; for(int i=0;i<board.length;i++) for(int j=0;j<board[0].length;j++){ boolean b = exist1(board,word,i,j,0); if(b) return true; } return false; } public boolean exist1(char[][] board,String word,int i,int j,int pos){ if(pos >= word.length()) return true; if(i<0 || j<0 || i>board.length-1 || j>board[0].length-1 || board[i][j]!=word.charAt(pos)) return false; board[i][j] += 256; boolean result = exist1(board,word,i-1,j,pos+1) || exist1(board,word,i+1,j,pos+1) || exist1(board,word,i,j-1,pos+1) || exist1(board,word,i,j+1,pos+1); board[i][j] -= 256; return result; } }
