当前位置: 面试刷题>> 单词搜索 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 示例代码

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

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

推荐面试题