题目描述

单词搜索 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 示例代码

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 进行单词检查。
• 维护一个访问矩阵来避免重复使用字符。
• 收集结果并返回。

在编写代码时，请确保遵循相同的逻辑结构和优化策略。