我正在为我的数据结构寻找一个好名字,它包含列表的所有"以开头"的子列表,例如:
Given list: [A, B, C]
My data structure: [ [A], [A, B], [A, B, C] ]
请注意,我的数据结构只包括有序组合(例如,不包括[C, B, A]
),而不包括所有组合(例如不包括[B, C]
)。只有所有前缀(在某种程度上)。
这种数据结构有正确的数学/编程术语吗?
使用TRIE。你可以在互联网上的资源上阅读更多关于这个数据结构的信息。
如果我们想要查找和前缀搜索这两种操作,Trie
是合适的。它主要用于字典和拼写检查器。使用Trie
,我们可以支持O(n)
时间中的所有操作,如插入、搜索、删除,其中n是要处理的单词的长度。
Trie的另一个优点是,我们可以按字母顺序打印所有单词。
使用Trie的缺点是它使用了更多的内存。要解决此问题,您可以阅读关于三元搜索树