単語検索のTrieツリーマッチ性能

Question

私はいくつかの同様の解決法をデバッグしていますが、Trie Treeを部分一致のプレフィックスに改善できるかどうか疑問です（Trieクラスの検索メソッドでは、現在の検索方法は完全な単語そうでない場合）、パフォーマンスを向上させることができます。私はそのアイデアには自信がないので、早期に助言を求める。

私は同様の解決策を投稿しています。ありがとう。

---

2Dボードと辞書からの単語のリストが与えられた場合、ボード内のすべての単語を探します。

各単語は、連続した隣接セルの文字から構成する必要があります。「隣接セル」は、水平または垂直に隣接するセルです。同じ文字セルを単語に複数回使用することはできません。例えば

、 考えると言葉= ["oath","pea","eat","rain"]とボード=

[ 
    ['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一部から間違った何も表示されません。あなたのコード。

しかし、トライのオリジナルのデザインは、不一致を検出したときにすでに早期復帰していると思います。

実際には、私は通常、問題を過度に複雑にすることを避けるために、defaultDict + TrieNodeではなく、通常はdictをトライとして使用します。特定のノードが有効な単語の場合は、"#"キーを設定するだけです。そして、挿入の間に、ちょうどnode[w] = {}をしてください。

これを行うと、ノードに「間違った」キーがまったくないので、コードを大幅に簡素化でき、早期返却が簡単になります！

たとえば、'ab'のみを含む単純なトライは、{'a': {'b': {'#': {}}}のようになります。したがって'cd'を検索すると、最も外側のdictにキー'c'が存在しなくなるとすぐにfalseを返すことができます。この実装はあなたのものと似ていますが、理解しやすいと思います。