Результат сопоставления дерева деревьев в поиске слов

Question

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

Я размещаю одно из подобных решений. Благодарю.

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

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

Например, Учитывая слова = ["oath","pea","eat","rain"] и доска =

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

Return [ "съесть", "присягу"]

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 уже имеет раннее возвращение при обнаружении какого-либо несоответствия.

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

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

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