Autocomplete

###自动完成 自动完成是一项我们都非常熟悉的功能。 但它实际上是如何工作的？ 你可以想象一个算法，它会取一个单词的前几个字母，将它们与一个已知单词列表进行比较，然后生成一个以给定字母开头的所有单词的列表。 这行得通，但想象一下我们正在为整个英语语言这样做——大约有 25 万个单词！ 这会起作用，但最终会很慢。 那么，我们的手机如何能够如此快速地自动完成我们正在输入的内容？ 尽管无法将输入的字母与所有已知单词进行比较，但有一种更有效的方法来存储已知单词，这将使这些单词的检索速度更快。 这种数据结构称为前缀树或特里树。 ###前缀树 前缀树（或 ）是一种树结构，其中树中的每个点都是一个字母，并包含可能紧接在下一个字母的列表。 这意味着从树的顶部开始，我们可以沿着树向下工作，从每个节点的字母开始构建单词。 这是一个图表： c |\ a u /