当前位置： 面试刷题>> 单词矩阵 (经典算法题500道)
### 题目描述补充
**单词矩阵（Word Matrix）**
给定一个二维字符矩阵（矩阵中的每个元素都是一个字符），和一个单词列表。请编写一个函数，用于找出所有在矩阵中通过水平、垂直、对角线（两个方向）或反对角线（两个方向）方式能够完整出现的单词。单词在矩阵中的路径可以是连续的字符序列，且路径上的每个字符恰好只被使用一次。
**示例输入**：
- 矩阵：
```
[
['a','b','c','e'],
['s','f','c','s'],
['a','d','e','e']
]
```
- 单词列表：`["abc", "es", "cfs"]`
**示例输出**：
- `["abc", "es"]`
注意：`"cfs"` 不在输出中，因为它不是通过连续路径形成的（尽管字符都存在，但它们不是连续的）。
### PHP 示例代码
```php
function findWords(array $board, array $words) {
$result = [];
$trie = new Trie();
foreach ($words as $word) {
$trie->insert($word);
}
$rows = count($board);
$cols = count($board[0]);
for ($i = 0; $i < $rows; $i++) {
for ($j = 0; $j < $cols; $j++) {
if ($board[$i][$j] != '#') { // 假设'#'不是单词中的字符
dfs($board, $i, $j, $trie->root, $result);
}
}
}
return $result;
}
class TrieNode {
public $children = [];
public $isWord = false;
}
class Trie {
public $root;
public function __construct() {
$this->root = new TrieNode();
}
public 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 dfs(&$board, $i, $j, $node, &$result) {
$char = $board[$i][$j];
$board[$i][$j] = '#'; // 标记已访问
if (isset($node->children[$char])) {
$node = $node->children[$char];
if ($node->isWord) {
$result[] = substr(implode('', array_keys($node->children)), 0, -1);
$node->isWord = false; // 防止重复添加
}
// 四个方向搜索
$directions = [[0, 1], [1, 0], [1, 1], [1, -1]];
foreach ($directions as $dir) {
$ni = $i + $dir[0];
$nj = $j + $dir[1];
if ($ni >= 0 && $ni < count($board) && $nj >= 0 && $nj < count($board[0])) {
dfs($board, $ni, $nj, $node, $result);
}
}
}
$board[$i][$j] = $char; // 恢复字符
}
// 使用示例
$board = [
['a','b','c','e'],
['s','f','c','s'],
['a','d','e','e']
];
$words = ["abc", "es", "cfs"];
print_r(findWords($board, $words));
```
### 注意
- 上述代码示例中，使用了 Trie 树（前缀树）来快速匹配单词。
- DFS（深度优先搜索）用于在矩阵中搜索所有可能的路径。
- 示例代码假定输入的矩阵和单词列表是有效的，没有进行错误处理。
### Python 和 JavaScript 示例
由于篇幅限制，这里只提供了 PHP 的详细实现。Python 和 JavaScript 的实现逻辑相似，只是语法和类库的使用有所不同。在 Python 中，你可以使用字典来构建 Trie 树，而在 JavaScript 中，可以使用对象或 Map。DFS 的逻辑在三种语言中都是相似的，只是遍历和修改数组/矩阵的语法不同。
**码小课**网站中有更多关于算法和数据结构的内容，包括各种搜索算法、Trie 树等，欢迎大家学习交流。