当前位置: 面试刷题>> 单词矩阵 (经典算法题500道)


题目描述补充

单词矩阵(Word Matrix)

给定一个二维字符矩阵(矩阵中的每个元素都是一个字符),和一个单词列表。请编写一个函数,用于找出所有在矩阵中通过水平、垂直、对角线(两个方向)或反对角线(两个方向)方式能够完整出现的单词。单词在矩阵中的路径可以是连续的字符序列,且路径上的每个字符恰好只被使用一次。

示例输入

  • 矩阵:
    [
      ['a','b','c','e'],
      ['s','f','c','s'],
      ['a','d','e','e']
    ]
    
  • 单词列表:["abc", "es", "cfs"]

示例输出

  • ["abc", "es"]

注意:"cfs" 不在输出中,因为它不是通过连续路径形成的(尽管字符都存在,但它们不是连续的)。

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 树等,欢迎大家学习交流。

推荐面试题