# [LeetCode] 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. 【解释】 给定一个二维的字符数组和一个单词，要求返回该单词是否可以在该字符数组中找到（查找尽可以上下左右查找） 【思路】 从数组的每一个位置上下左右递归查找，如果有任意方向找到则返回true，否则从下一个位置开始查找。

```public class Solution {
public static boolean exitCore(char[][] board,String word, int index, int row,int col,boolean[][] isVisit){
if(index==word.length()) return true;//前面所有的元素都相等，则找到
if(row<0||col<0||row>=board.length||col>=board[0].length||
board[row][col]!=word.charAt(index)||isVisit[row][col])
return false;
boolean flag=false;
isVisit[row][col]=true;
flag=exitCore(board, word, index+1,row+1,col,isVisit)||exitCore(board, word, index+1,row,col+1,isVisit)
||exitCore(board, word, index+1,row-1,col,isVisit)||exitCore(board, word, index+1,row,col-1,isVisit);
if(flag) return flag;
isVisit[row][col]=false;//没有找到，重新将该元素置为未访问
return false;
}
public static boolean exist(char[][] board, String word) {
int m=board.length,n=board[0].length;
boolean[][] isVisit=new boolean[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++)
if(exitCore(board,word,0,i,j,isVisit)) return true;

}
return false;
}

}```

50 篇文章33 人订阅

0 条评论

## 相关文章

### UESTC 485 Game（康托，BFS）

Today I want to introduce an interesting game to you. Like eight puzzle, it is a...

2677

1983

542

1484

652

1868

1440

2673