我们都用过主流搜索引擎，谷歌、必应，当然还有搜狗、百度等。当你搜索一个关键词时，它会在下拉框中填充一些热门的关键词，如下图所示：

搜索关键字提示

当您点击一个关键词时，页面会直接跳转到结果页面，结果页面会显示搜索关键词提示功能，在一定程度上节省了用户的搜索时间。

节省时间的方法很有价值，值得学习和使用。

但是，在公司内部的许多系统中，此功能未包含在搜索框中。如果你能实现这个功能，那么你的用户在使用的时候肯定会眼花缭乱，他们会对它有很好的印象，领导看到后也会给你竖起大拇指。

这个功能实现起来非常简单，每次在前端输入一个字符，就可以去后端查询同一个关键词，然后退出再返回到下拉列表。前端的实现在网上搜索量很大，比如搜索关键词“搜索框自动补全”，结果很多，这里就不多说了。以下是实现后端的方法。

如果关键词的数量不多，我们可以使用最简单的字符串匹配算法，比如BF算法，就是遍历所有关键词，找出pre-drop和输入字符串之间的匹配，然后返回到前端，语言也提供了这种字符串的方法，更容易实现， 简单意味着不容易犯错误，没有错误，在关键词很少的情况下，这种方法可以是首选。

如果你有大量的关键词，你需要考虑性能问题，而trie树就是能够有效解决这个问题的数据结构。让我们看一下前一个辍学树的示意图

特里树

这个树的根节点不存储数据，其他节点保存关键词信息，如、her、hi、how、see、so等，如果你查到he的单词，你可以快速返回，her。

这类树的子节点的数据不是固定的，通用算法教程通过固定每个节点的指针数量来降低实现的难度，比如使用一个个个用字符映射的下标数组来存储子节点的指针，如下图所示：

一种方法

这种结构效率很高，但是浪费空间，如果关键词有中文或标点符号，就不能重复使用。

幸运的是，该语言有一个高效的数据结构，称为字典，它很容易实现：键可以用作父节点，值可以用作子节点，值是包含所有子节点信息的字典。让我们先感受一下

登录后复制

• 1.

{'中'：{-1：True，'国'：{-1：True，'人'：{-1：True}}，'华'：{'人'：{'民'：{'共'：{'和'：{'国'：{-1：True}}}}}}}}

这里 -1 为 true，表示这已经是一个完整的候选者，上面的字典树表示以下关键字：

登录后复制

• 1.

中等

中国

中文

中华人民共和国

Trie 树的实现：

那里

是 Trie 树中的三个主要操作，第一个是将关键字插入到 Trie 树中，第二个是查询 Trie 树中的一个关键字，第三个是返回 Trie 树中给定的 中的所有关键字。这并不难实现，这是我的方法之一：

登录后复制

• 1.

#=UTF-8

（）：

（自身）：

“””

。

“””

self.root={}

self.end=-1

（自我，字）：

“””

理氏。

：：str

：：无效

“””

=自我.根

：

：

[c]={}

=[c]

[self.end]=真

（自我，字）：

“””

。

：：str

：：布尔

“””

=自我.根

：

：

=[c]

#'

.：

（自身，）：

“””

。

：：str

：：布尔

“””

=自我.根

：

：

=[c]

（自身，）：

'''

给定一个 ，将打印所有匹配的字符串

：：

：：

'''

（前，）：

=[]

.get（self.end）：

。（前）

.keys（）：

！=self.end：

。（（pre+key，.get（key）））

。():

[]

还：

节点=self.root

：

节点=node.get（p）

还：

（，节点）

==“”：

trie=Trie（）

尝试。("")

尝试。（“算法”）。

尝试。("")

尝试。（“发展”）。

尝试。（“开发视频教程”

）。

尝试。（“算法源”）。

尝试。（“Perl 算法源”）。

（尝试。Perl“））

（尝试。Perl算法源代码“））。

（（trie.（'P')))

（（trie.（''）

（（trie.（'计数'））））。

（（trie.（'P')))

（（trie.（''）

（（trie.（'计数'））））。

代码按如下方式运行：

登录后复制

• 1.

真

[''，'算法'，'算法源'，''，'开发'，'开发视频教程'，'Perl算法源']。

[''，'开发'，'开发视频教程']。

['算法'， '算法源']。

Trie 的时间复杂性

如果您想频繁查询一组关键字中的某些关键字，使用 Trie 树可以非常有效。构建 Trie 树的过程需要扫描所有关键字，时间复杂度为 O（n）（n 表示所有关键字的长度之和）。但是，一旦构建成功，后续的查询操作将非常高效。

我们每次查询时，如果要查询的关键词长度是k，那么我们最多只需要比较k个节点就可以完成查询操作了。它与原始组中关键字的长度和数量无关。因此，在构建 Trie 树后，在其中查找关键字的时间复杂度为 O（k），k 是要查找的关键字的长度。

如果您不想构建轮子下拉框关键词，请学习 -trie

构建自己的轮子也需要思考、编码和验证，但这是学习和改进的最佳方式。如果你急着申请，没有时间做轮子，至少要学习如何使用轮子，下面这个前辍学树的轮子是日本人写的，你可以学习应用它。

写在最后

以上只是实现搜索框智能提示的小步骤，在实际使用中，你也可能会遇到以下问题：

1.如果候选人太多，他们应该如何选择性地显示哪些关键词？

2. 如果用户犯了错误，如何仍能按照正确的拼写显示候选关键词？

第一个问题很容易解决，我们可以根据搜索的频率或关键词的搜索结果数量，自动为每个关键词生成一个权重数，并根据权重有选择地从大到小显示前n个项目。

第二个问题涉及到动态规划，你可以先思考，有时间的话再写一篇文章。

其实Trie树在自动补全的需求上可以起到一定的作用，比如输入法的自动补全功能，IDE代码编辑器的自动补全功能，浏览器URL输入的自动补全功能。