## 题目地址

https://leetcode.com/problems/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 =

``````[
["ABCE"],
["SFCS"],
]

``````

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

## 思路

``````class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if (board.empty() || board[0].empty()) return false;
int m = board.size(), n = board[0].size();
vector<vector<bool>> visited(m, vector<bool>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++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;
int m = board.size(), n = board[0].size();
if (i < 0 || j < 0 || i >= m || j >= n || 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;
}
};

``````

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

### 思路2

1. 扫描二维数组，找到board[1,0] = word[0]，匹配单词首字母。
2. 做DFS（上，下，左，右 四个方向）

1. 标记当前字符（1，0）为已经访问过，board[1][0] = '*'
2. 上（0，0）字符为 'A' 不匹配,
3. 下（2，0）字符为 'A'，不匹配,
4. 左（-1，0）超越边界，不匹配,
5. 右（1，1）字符 'F'，不匹配

1. 回溯，标记起始位置（1，0）为未访问。board[1][0] = 'S'.
2. 然后继续扫描二维数组，找到下一个起始位置（1，3）

1. 标记当前字符（1, 3）为已经访问过，board[1][3] = '*'
2. 上（0，3）字符为 'E', 匹配, 继续DFS搜索（参考位置为（0，3）位置DFS搜索步骤描述）
3. 下（2，3）字符为 'E'，匹配, #2匹配，先进行#2 DFS搜索，由于#2 DFS搜索没有找到与单词匹配，继续DFS搜索（参考位置为（2，3）DFS搜索步骤描述）
4. 左（1，2）字符为 'C'，不匹配,
5. 右（1，4）超越边界，不匹配

1. 标记当前字符（0，3）为已经访问过，board[0][3] = '*'
2. 上 （-1，3）超越边界，不匹配
3. 下（1，3）已经访问过，
4. 左（0，2）字符为 'C'，不匹配
5. 右（1，4）超越边界，不匹配

1. 回溯，标记起始位置（0，3）为未访问。board[0][3] = 'E'.
2. 回到满足条件的位置（2，3），继续DFS搜索，判断相邻的字符是否匹配单词下一个字符 'E'
3. 上 (1，3）已访问过
4. 下（3，3）超越边界，不匹配
5. 左（2，2）字符为 'E'，匹配
6. 右（2，4）超越边界，不匹配

#### 复杂度分析

• 时间复杂度： `O(m*n) - m 是二维数组行数， n 是二维数组列数`
• 空间复杂度： `O(1) - 这里在原数组中标记当前访问过，没有用到额外空间`

## 关键点解析

• 遍历二维数组的每一个点，找到起始点相同的字符，做DFS
• DFS过程中，要记录已经访问过的节点，防止重复遍历，这里（Java Code中）用 `*` 表示当前已经访问过，也可以用Set或者是boolean[][]数组记录访问过的节点位置。
• 是否匹配当前单词中的字符，不符合回溯，这里记得把当前 `*` 重新设为当前字符。如果用Set或者是boolean[][]数组，记得把当前位置重设为没有访问过。

## 代码

Java Code

``````public class LC79WordSearch {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0
|| word == null || word.length() == 0) return true;
int rows = board.length;
int cols = board[0].length;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == word.charAt(0)) {
if (helper(board, word, r, c, 0)) {
return true;
}
}
}
}
return false;
}

private boolean helper(char[][] board, String word, int r, int c, int start) {
// already match word all characters, return true
if (start == word.length()) return true;
if (!isValid(board, r, c) ||
board[r][c] != word.charAt(start)) return false;
// mark visited
board[r][c] = '*';
boolean res = helper(board, word, r - 1, c, start + 1) // 上
||  helper(board, word, r + 1, c, start + 1)       // 下
||  helper(board, word, r, c - 1, start + 1)       // 左
||  helper(board, word, r, c + 1, start + 1);      // 右
// backtracking to start position
board[r][c] = word.charAt(start);
return res;
}

private boolean isValid(char[][] board, int r, int c) {
return r >= 0 && r < board.length && c >= 0 && c < board[0].length;
}
}
``````

Python3 Code

``````class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m = len(board)
n = len(board[0])

def dfs(board, r, c, word, index):
if index == len(word):
return True
if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[index]:
return False
board[r][c] = '*'
res = dfs(board, r - 1, c, word, index + 1) or dfs(board, r + 1, c, word, index + 1) or dfs(board, r, c - 1, word, index + 1) or dfs(board, r, c + 1, word, index + 1)
board[r][c] = word[index]
return res

for r in range(m):
for c in range(n):
if board[r][c] == word[0]:
if dfs(board, r, c, word, 0):
return True
``````

Javascript Code from @lucifer

``````/*
* @lc app=leetcode id=79 lang=javascript
*
* [79] Word Search
*/
function DFS(board, row, col, rows, cols, word, cur) {
// 边界检查
if (row >= rows || row < 0) return false;
if (col >= cols || col < 0) return false;

const item = board[row][col];

if (item !== word[cur]) return false;

if (cur + 1 === word.length) return true;

// 如果你用hashmap记录访问的字母， 那么你需要每次backtrack的时候手动清除hashmap，并且需要额外的空间
// 这里我们使用一个little trick

board[row][col] = null;

// 上下左右
const res =
DFS(board, row + 1, col, rows, cols, word, cur + 1) ||
DFS(board, row - 1, col, rows, cols, word, cur + 1) ||
DFS(board, row, col - 1, rows, cols, word, cur + 1) ||
DFS(board, row, col + 1, rows, cols, word, cur + 1);

board[row][col] = item;

return res;
}
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
if (word.length === 0) return true;
if (board.length === 0) return false;

const rows = board.length;
const cols = board[0].length;

for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
const hit = DFS(board, i, j, rows, cols, word, 0);
if (hit) return true;
}
}
return false;
};
``````

评论
0 评论