Trie 树在单词搜索中的匹配性能

Question

我已经调试了几个类似的解决方案，但想知道我们是否可以将 Trie Tree 改进为部分匹配前缀（在 class Trie 的搜索方法中，当前的搜索方法只检查是否匹配完整的单词) 甚至提高性能，这可能 return 更早地从错误的路径中走出来？对idea不是很自信，早点求教

我post类似的解决方案之一。谢谢

给定一个二维板和字典中的单词列表，找到板上的所有单词。

每个单词必须由连续相邻单元格的字母构成，其中 "adjacent" 单元格是水平或垂直相邻的单元格。同一个字母单元格不能在一个单词中使用多次。

例如，给定单词 = ["oath","pea","eat","rain"] 和 board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"]

class TrieNode():
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.isWord = False

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

    def insert(self, word):
        node = self.root
        for w in word:
            node = node.children[w]
        node.isWord = True

    def search(self, word):
        node = self.root
        for w in word:
            node = node.children.get(w)
            if not node:
                return False
        return node.isWord

class Solution(object):
    def findWords(self, board, words):
        res = []
        trie = Trie()
        node = trie.root
        for w in words:
            trie.insert(w)
        for i in xrange(len(board)):
            for j in xrange(len(board[0])):
                self.dfs(board, node, i, j, "", res)
        return res

    def dfs(self, board, node, i, j, path, res):
        if node.isWord:
            res.append(path)
            node.isWord = False
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
            return 
        tmp = board[i][j]
        node = node.children.get(tmp)
        if not node:
            return 
        board[i][j] = "#"
        self.dfs(board, node, i+1, j, path+tmp, res)
        self.dfs(board, node, i-1, j, path+tmp, res)
        self.dfs(board, node, i, j-1, path+tmp, res)
        self.dfs(board, node, i, j+1, path+tmp, res)
        board[i][j] = tmp

Answer 1

我没有发现您代码中的 Trie 部分有任何问题。

但我认为 trie 的原始设计在检测到任何不匹配时已经提前 returning。

实际上，我通常只使用正则 dict 作为 trie 而不是 defaultDict + TrieNode 以避免使问题过于复杂。如果某个节点是一个有效的词，你只需要设置一个 "#" 键。而且，在插入期间，只需执行 node[w] = {}.

如果你这样做，你的代码可以大大简化，并且早期 returning 会很简单，因为你根本不会在节点中有 "wrong" 键！

例如，仅包含 'ab' 的简单 trie 将如下所示：{'a': {'b': {'#': {}}}。所以当你搜索 'cd' 时，一旦发现最外层的字典中没有关键字 'c'，你就可以 return false。这个实现和你的类似，但我相信它更容易理解。

Trie 树在单词搜索中的匹配性能

Trie tree match performance in word search

python

algorithm

trie