algorithm - 查找以指定字符串开头的单词数的最快方法(单词存储在 AVL 树中)

Question

我已经实现了自己的 AVL 树，并将其用作字典。我想知道，计算以某个字符串开头的所有单词的最快方法是什么。

例如:

string prefix = "fa";

output: 4

我已经在 O(n) 内完成了它，但是，我听说它可以更快地完成。我当然可以在节点中保留其他信息，例如下面的节点和其他类似信息。

Answer 1

如果您愿意更改数据结构，您可以从 trie 获得卓越的性能.如果 trie 包含静态数据，您可以通过使用子树计数的大小(通过动态编程生成)注释分支来获得更好的性能。

例如 [竖琴、帽子、嗨]

           h(3)
      a(2)     i()
  r(1)    t()
p()