当前位置： 面试刷题>> 单词搜索 II(经典算法150题)
### 题目描述
**单词搜索 II**
给定一个二维网格 `board` 和一个单词列表 `words`，找出所有同时在二维网格中出现的单词。单词必须按照字母顺序连续地放置在网格中，包括网格的边界，并且单词中的每个字母只能使用一次。
**示例**：
```
board = [
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
words = ["oath","pea","eat","rain"]
输出: ["eat","oath"]
```
**注意**：
- 你可以假设所有输入都只包含小写字母 `a-z`。
- 网格中的字母可以重复使用于不同的单词搜索。
- 每个单词必须在网格中连续。
- 输入的单词列表 `words` 可以包含重复项，但在结果中每个单词只能出现一次。
### 解题思路
1. **前缀树（Trie）构建**：首先，将单词列表 `words` 构建成前缀树（Trie），以便快速检查当前路径上的字母是否可能构成一个单词。
2. **深度优先搜索（DFS）**：遍历网格的每个位置，对每个位置执行深度优先搜索，尝试找到以当前字符为起点的所有可能单词。
3. **剪枝优化**：在搜索过程中，使用前缀树来剪枝，如果当前路径上的字母不能构成任何单词的前缀，则回溯。
4. **标记访问过的字符**：为了避免重复使用字符，在访问过的字符上做标记，并在回溯时恢复。
### PHP 示例代码
```php
class TrieNode {
public $children;
public $isWord;
function __construct() {
$this->children = array();
$this->isWord = false;
}
}
class Trie {
public $root;
function __construct() {
$this->root = new TrieNode();
}
function insert($word) {
$node = $this->root;
for ($i = 0; $i < strlen($word); $i++) {
$char = $word[$i];
if (!isset($node->children[$char])) {
$node->children[$char] = new TrieNode();
}
$node = $node->children[$char];
}
$node->isWord = true;
}
}
function findWords($board, $words) {
$trie = new Trie();
foreach ($words as $word) {
$trie->insert($word);
}
$rows = count($board);
$cols = count($board[0]);
$result = [];
$visited = array_fill(0, $rows, array_fill(0, $cols, false));
for ($i = 0; $i < $rows; $i++) {
for ($j = 0; $j < $cols; $j++) {
dfs($board, $i, $j, $trie->root, '', $visited, $result);
}
}
return array_unique($result);
}
function dfs($board, $i, $j, $node, $currentWord, &$visited, &$result) {
if ($i < 0 || $i >= count($board) || $j < 0 || $j >= count($board[0]) || $visited[$i][$j]) {
return;
}
$char = $board[$i][$j];
if (!isset($node->children[$char])) {
return;
}
$visited[$i][$j] = true;
$currentWord .= $char;
if ($node->children[$char]->isWord) {
$result[] = $currentWord;
$node->children[$char]->isWord = false; // 防止重复添加
}
dfs($board, $i + 1, $j, $node->children[$char], $currentWord, $visited, $result);
dfs($board, $i - 1, $j, $node->children[$char], $currentWord, $visited, $result);
dfs($board, $i, $j + 1, $node->children[$char], $currentWord, $visited, $result);
dfs($board, $i, $j - 1, $node->children[$char], $currentWord, $visited, $result);
$visited[$i][$j] = false;
$currentWord = substr($currentWord, 0, -1);
}
// 示例使用
$board = [
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
];
$words = ["oath","pea","eat","rain"];
$result = findWords($board, $words);
print_r($result);
```
### Python 和 JavaScript 示例
由于篇幅限制，这里不直接提供完整的 Python 和 JavaScript 示例代码，但基本思路与 PHP 示例相同，你需要：
- 创建一个 Trie 类来管理单词列表。
- 实现一个深度优先搜索函数来遍历网格，并使用 Trie 进行单词检查。
- 维护一个访问矩阵来避免重复使用字符。
- 收集结果并返回。
在编写代码时，请确保遵循相同的逻辑结构和优化策略。