词搜索中的树匹配性能

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']
]

Return[“吃”，“发誓”]

^{pr2}$

Answer 1

我看不出代码中Trie部分有任何错误。在

但我认为trie最初的设计已经在检测到任何不匹配时提前返回。在

实际上，我通常只使用正则的dict作为trie，而不是{}，以避免问题变得过于复杂。如果某个节点是有效的单词，则只需设置"#"键。在插入过程中，只需执行node[w] = {}。在

如果您这样做，您的代码可以大大简化，并且早期返回将是直接的，因为您将不会有一个“错误的”键在一个节点！在

例如，一个只包含'ab'的简单trie看起来像：{'a': {'b': {'#': {}}}。因此，当您搜索'cd'时，一旦您意识到最外面的dict中没有键'c'，就可以返回false。这个实现与您的类似，但是我相信它更容易理解。在