当前位置： 面试刷题>> 单词搜索 (经典算法题500道)
### 题目描述
**单词搜索**：给定一个二维网格（board）和一个单词（word），找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的格子里的字母构成，其中“相邻”格子是指水平或垂直方向上相邻的格子。同一个格子里的字母在一个单词中不允许被重复使用。
### 示例
**输入**：
- 二维网格 `board`:
```
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
```
- 单词 `word`: "ABCCED"
**输出**:
- `true`，因为单词 "ABCCED" 可以通过路径 "A" -> "B" -> "C" -> "C" -> "E" -> "D" 在网格中被找到。
### PHP 示例代码
```php
function exist($board, $word) {
$rows = count($board);
$cols = count($board[0]);
for ($i = 0; $i < $rows; $i++) {
for ($j = 0; $j < $cols; $j++) {
if (dfs($board, $word, 0, $i, $j)) {
return true;
}
}
}
return false;
}
function dfs(&$board, $word, $index, $row, $col) {
$rows = count($board);
$cols = count($board[0]);
if ($index == strlen($word)) {
return true;
}
if ($row < 0 || $row >= $rows || $col < 0 || $col >= $cols || $board[$row][$col] != $word[$index]) {
return false;
}
$temp = $board[$row][$col];
$board[$row][$col] = '#'; // 标记当前格子已访问
$directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // 上下左右四个方向
foreach ($directions as $dir) {
$newRow = $row + $dir[0];
$newCol = $col + $dir[1];
if (dfs($board, $word, $index + 1, $newRow, $newCol)) {
return true;
}
}
$board[$row][$col] = $temp; // 恢复格子状态
return false;
}
```
### Python 示例代码
```python
def exist(board, word):
if not board or not board[0] or not word:
return False
rows, cols = len(board), len(board[0])
def dfs(i, j, index):
if index == len(word):
return True
if i < 0 or i >= rows or j < 0 or j >= cols or board[i][j] != word[index]:
return False
temp = board[i][j]
board[i][j] = '#' # 标记已访问
found = dfs(i - 1, j, index + 1) or \
dfs(i + 1, j, index + 1) or \
dfs(i, j - 1, index + 1) or \
dfs(i, j + 1, index + 1)
board[i][j] = temp # 恢复格子状态
return found
for i in range(rows):
for j in range(cols):
if dfs(i, j, 0):
return True
return False
```
### JavaScript 示例代码
```javascript
function exist(board, word) {
if (!board || !board[0] || !word) return false;
const rows = board.length;
const cols = board[0].length;
const dfs = (i, j, index) => {
if (index === word.length) return true;
if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] !== word[index]) return false;
const temp = board[i][j];
board[i][j] = '#'; // 标记已访问
const found = dfs(i - 1, j, index + 1) ||
dfs(i + 1, j, index + 1) ||
dfs(i, j - 1, index + 1) ||
dfs(i, j + 1, index + 1);
board[i][j] = temp; // 恢复格子状态
return found;
};
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (dfs(i, j, 0)) return true;
}
}
return false;
}
```
### 码小课提示
在码小课网站上，你可以找到更多关于算法和数据结构的详细讲解和练习，包括回溯算法、深度优先搜索（DFS）、广度优先搜索（BFS）等高级主题，帮助你更深入地理解和应用这些算法解决实际问题。