当前位置： 面试刷题>> 单词搜索(经典算法150题)
### 题目描述
**单词搜索（Word Search）**
给定一个二维网格（board）和一个单词（word），判断该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是指水平或垂直方向上相邻的单元格。同一个单元格内的字母不允许被重复使用。
**示例 1**:
```
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED"
输出: true
```
**示例 2**:
```
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "SEE"
输出: true
```
**示例 3**:
```
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCB"
输出: false
```
### 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;
}
// 使用示例
$board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
];
$word = "ABCCED";
var_dump(exist($board, $word)); // 输出: bool(true)
```
### Python 示例代码
```python
def exist(board, word):
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
# 使用示例
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED"
print(exist(board, word)) # 输出: True
```
### JavaScript 示例代码
```javascript
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
const dfs = (row, col, index) => {
if (index === word.length) return true;
if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] !== word[index]) {
return false;
}
const temp = board[row][col];
board[row][col] = '#'; // 标记为已访问
const found = dfs(row - 1, col, index + 1) || // 上
dfs(row + 1, col, index + 1) || // 下
dfs(row, col - 1, index + 1) || // 左
dfs(row, col + 1, index + 1); // 右
board[row][col] = 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;
}
// 使用示例
const board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
];
const word = "ABCCED";
console.log(exist(board, word)); // 输出: true
```
这些示例展示了如何使用深度优先搜索（DFS）算法来解决单词搜索问题。每个示例都包含了一个辅助的DFS函数，用于递归地探索网格，并判断是否存在从当前位置开始的路径，能够按顺序匹配给定的单词。