79.单词搜索

79. 单词搜索

难度中等502

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

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

示例:

board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

		//dfspublic boolean exist(char[][] board, String word) {char [] words = word.toCharArray();for(int i=0;i<board.length;i++){for(int j=0;j<board[0].length;j++){if(dfs(board,words,i,j,0)){return true;}}}return false;}private boolean dfs(char [][] board, char [] words,int i,int j,int k){if(i<0 || j < 0 || i>=board.length || j>=board[0].length){//边界判断return false;}if(board[i][j]!=words[k]){//不符合return false;}if(words.length-1 == k){return true;}//决策char tmp = board[i][j];board[i][j] = '*';boolean res = dfs(board,words,i+1,j,k+1) || dfs(board,words,i-1,j,k+1)  //上下左右穷举|| dfs(board,words,i,j+1,k+1) || dfs(board,words,i,j-1,k+1);//注意//k+1 和 k++ 的区别，k++是改变了k的值 当回溯的时候 原来的1不会改变成1 而就是2 而k+1 只是在递归的下一层的时候 值进行了加1 而在回溯的时候，还是1 这是一点区别board[i][j] = tmp;//取消决策return res;}