[212][困难][DFS] 单词搜索 II

题目描述

212. 单词搜索 II

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

输入:
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

输出: ["eat","oath"]

说明:

• 你可以假设所有输入都由小写字母 a-z 组成。

提示:

• 你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？

• 如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题：实现Trie（前缀树）。

解题思路

DFS + Trie树

[[剑指Offer-12][中等][DFS] 矩阵中的路径的扩展版. 搜索是否包含多个单词, 使用前缀Trie树减少遍历次数. DFS的思路与前面题目中的一样, 只是剪枝条件变了:

• 索引超越边界, 剪枝

• 当前前缀不在树中, 剪枝

搜索到单词就添加到结果中, 但不能停止, 因为可能是另一个单词的前缀.

class Trie:
    def __init__(self):
        self.root = dict()

    def insert(self, word):
        root = self.root
        for c in word + '&':
            if c not in root:
                root[c] = dict()
            root = root[c]

    @lru_cache(None)
    def search(self, word):
        root = self.root
        for c in word:
            if c not in root:
                return False
            root = root[c]
        return True if '&' in root else False

    @lru_cache(None)
    def startwith(self, prefix):
        root = self.root
        for c in prefix:
            if c not in root:
                return False
            root = root[c]
        return True


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        n, m = len(board), len(board[0])
        trie = Trie()
        for w in words:
            trie.insert(w)

        res = set()

        def dfs(i, j, prefix):
            if not 0 <= i < n or not 0 <= j < m:
                return False
            new_prefix = prefix + board[i][j]
            if not trie.startwith(new_prefix):
                return False
            if trie.search(new_prefix):
                res.add(new_prefix)

            tmp, board[i][j] = board[i][j], '/'
            t = dfs(i + 1, j, new_prefix) or dfs(i - 1, j, new_prefix) or dfs(i, j + 1, new_prefix) or dfs(i, j - 1, new_prefix)
            board[i][j] = tmp
            return t

        for i in range(n):
            for j in range(m):
                dfs(i, j, '')
        return list(res)