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

Question

我已经调试了一些类似的解决方案,但想知道我们是否可以将Trie Tree改进为部分匹配前缀(在Trie类的搜索方法中,当前搜索方法仅检查是否匹配完整的单词)甚至可以提高性能,这可能会返回从较早的错误路径？我对这个想法不是很有信心,所以早点寻求建议.

我发布了一个类似的解决方案.谢谢.

---

给定2D板和字典中的单词列表,找到板中的所有单词.

每个字必须由顺序相邻的单元的字母构成,其中"相邻"单元是水平或垂直相邻的单元.一个单词中不能多次使用相同的字母单元格.

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

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

返回["吃","誓言"]

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在代码中的部分没有看到任何错误.

但我认为,当检测到任何不匹配时,特里的原始设计已经提前返回.

实际上,我通常只使用常规dict作为trie而不是defaultDict + TrieNode避免使问题过于复杂."#"如果某个节点是有效字,您只需要设置一个键.而且,在插入过程中,就这样做node[w] = {}.

如果你这样做,你的代码可以大大简化,并且提前返回将是直截了当的,因为你根本就没有节点中的"错误"键!

例如,仅包含的简单trie 'ab'将如下所示:{'a': {'b': {'#': {}}}.所以当你搜索时'cd',一旦你意识到'c'最外面的字典中没有键,你就可以返回false.这种实现与您的实现类似,但我相信它更容易理解.