# [LeetCode] 79. Word Search 单词搜索

2021年09月15日 阅读数：1

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

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.java

For example,
Given board =python

```[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
```

word = `"ABCCED"`, -> returns `true`,
word = `"SEE"`, -> returns `true`,
word = `"ABCB"`, -> returns `false`.数组

1.数组越界。2.该点已访问过。3.该点的字符和word对应的index字符不匹配。spa

Java:code

```public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;

boolean result = false;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(dfs(board,word,i,j,0)){
result = true;
}
}
}

return result;
}

public boolean dfs(char[][] board, String word, int i, int j, int k){
int m = board.length;
int n = board[0].length;

if(i<0 || j<0 || i>=m || j>=n){
return false;
}

if(board[i][j] == word.charAt(k)){
char temp = board[i][j];
board[i][j]='#';
if(k==word.length()-1){
return true;
}else if(dfs(board, word, i-1, j, k+1)
||dfs(board, word, i+1, j, k+1)
||dfs(board, word, i, j-1, k+1)
||dfs(board, word, i, j+1, k+1)){
return true;
}
board[i][j]=temp;
}

return false;
}　```

Java：htm

```class Solution {
int[] dh = {0, 1, 0, -1};
int[] dw = {1, 0, -1, 0};

public boolean exist(char[][] board, String word) {
boolean[][] isVisited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++)
for (int j = 0; j < board[0].length; j++)
if (isThisWay(board, word, i, j, 0, isVisited)) return true;
return false;
}

public boolean isThisWay(char[][] board, String word, int row, int column, int index, boolean[][] isVisited) {
if (row < 0 || row >= board.length || column < 0 || column >= board[0].length
|| isVisited[row][column] || board[row][column] != word.charAt(index))
return false;  //剪枝
if (++index == word.length()) return true;  //word全部字符均匹配上
isVisited[row][column] = true;
for (int i = 0; i < 4; i++)
if (isThisWay(board, word, row + dh[i], column + dw[i], index, isVisited))
return true;  //以board[row][column]为起点找到匹配上word路径
isVisited[row][column] = false;  //遍历事后，将该点还原为未访问过
return false;
}
}　　```

Python：

```class Solution:
# @param board, a list of lists of 1 length string
# @param word, a string
# @return a boolean
def exist(self, board, word):
visited = [[False for j in xrange(len(board[0]))] for i in xrange(len(board))]

for i in xrange(len(board)):
for j in xrange(len(board[0])):
if self.existRecu(board, word, 0, i, j, visited):
return True

return False

def existRecu(self, board, word, cur, i, j, visited):
if cur == len(word):
return True

if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or visited[i][j] or board[i][j] != word[cur]:
return False

visited[i][j] = True
result = self.existRecu(board, word, cur + 1, i + 1, j, visited) or\
self.existRecu(board, word, cur + 1, i - 1, j, visited) or\
self.existRecu(board, word, cur + 1, i, j + 1, visited) or\
self.existRecu(board, word, cur + 1, i, j - 1, visited)
visited[i][j] = False

return result
```

C++：

```class Solution {
public:
bool exist(vector<vector<char> > &board, string word) {
if (word.empty()) return true;
if (board.empty() || board[0].empty()) return false;
vector<vector<bool> > visited(board.size(), vector<bool>(board[0].size(), false));
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[i].size(); ++j) {
if (search(board, word, 0, i, j, visited)) return true;
}
}
return false;
}
bool search(vector<vector<char> > &board, string word, int idx, int i, int j, vector<vector<bool> > &visited) {
if (idx == word.size()) return true;
if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || visited[i][j] || board[i][j] != word[idx]) return false;
visited[i][j] = true;
bool res = search(board, word, idx + 1, i - 1, j, visited)
|| search(board, word, idx + 1, i + 1, j, visited)
|| search(board, word, idx + 1, i, j - 1, visited)
|| search(board, word, idx + 1, i, j + 1, visited);
visited[i][j] = false;
return res;
}
};　```

[LeetCode] 212. Word Search II 词语搜索 II

[LeetCode] 348. Design Tic-Tac-Toe 设计井字棋游戏