Эффективность соответствия Trie tree в поиске слов

Я отлаживаю несколько подобных решений, но задаюсь вопросом, можем ли мы улучшить Trie Tree до префикса частичного совпадения (в методе поиска класса Trie, текущий метод поиска проверяет только совпадение полного слова или нет) даже повысить производительность, который может вернуться с неправильного пути раньше? Я не очень уверен в этой идее, поэтому ищите совета раньше.

Я размещаю одно из подобных решений. Спасибо.

Учитывая двумерную доску и список слов из словаря, найдите все слова на доске.

Каждое слово должно быть построено из букв последовательно соседней ячейки, где "смежные" ячейки являются горизонтальными или вертикальными соседями. Одна и та же ячейка письма не может использоваться более одного раза в слове.

Например, С учетом слов = ["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

Ответы

Ответ 1

Я не вижу ничего плохого в части Trie в вашем коде.

Но я думаю, что первоначальный дизайн trie уже имеет раннее возвращение при обнаружении какого-либо несоответствия.

На самом деле, я обычно использую обычный dict как trie вместо defaultDict + TrieNode, чтобы избежать чрезмерной сложности проблемы. Вам просто нужно установить ключ "#", если определенное node является допустимым словом. И во время вставки просто node[w] = {}.

Если вы это сделаете, ваш код может быть значительно упрощен, и раннее возвращение будет простым, так как вы не будете иметь "неправильный" ключ в node вообще!

Например, простое trie, содержащее только 'ab', будет выглядеть так: {'a': {'b': {'#': {}}}. Поэтому, когда вы ищете 'cd', как только вы поняли, что в самом внешнем dict нет ключа 'c', вы можете вернуть false. Эта реализация похожа на вашу, но я считаю, что ее легче понять.