当我们键入一半的命令或名称并按下 Tab 键时,它会立即找出剩余的部分。下面使用什么数据结构/算法来实现这种效率?
最佳答案
A trie是一个很好的数据结构来解决这个问题。
这是一棵树,其中每条边代表下一个可能的字符,该字符将附加到由从根开始的当前路径定义的字符串。
因此,如果您要输入 in
,您将沿着 root -i-> i -n-> in
移动,并探索该子树以找到 客栈
.
您可以在每个节点上包含一个标志以指示它是否包含有效单词(对于非叶子,因为只有在包含有效单词时才会创建叶子)。
可以使用的一种更常见(但不太专业)的数据结构是 binary search tree (BST) .
A binary search tree (BST) ... is a node-based binary tree data structure where each node has a comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right sub-tree.
根据 BST 的实现,您应该能够:
调用
range
函数来获取两个值之间的所有元素,特别是字符串与其“增量”之间的元素。例如,如果给定abc
,则“递增”字符串将为abd
。如果给定abz
,“递增”字符串将是aca
(假设我们只允许在 BST 中使用a-z
,否则您可以只选择字符在字符集中的z
之后,例如 ASCII 中的{
)。调用
ceiling
类型的函数获取大于或等于给定字符串的最小元素,然后重复获取中序后继,直到获取的元素不再以给定的字符串。
关于algorithm - 什么数据结构或算法用于自动完成?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23152937/