algorithm - 来自文本文件的单词建议的数据结构

Question

问题:给定一个包含多行文本的文本文件。现在用户将输入几个字母，我们必须根据给定的文件中的文本给出自动完成建议。假设文件包含 computer science is fun。计算机工程很棒。现在，如果用户键入 com，我们需要给出 computer science 和 computer engineering 作为建议。如果用户键入 is，建议应该是 fun 和 awesome。用户可以输入文本文件中可能存在或不存在的任何单词。如果该词不在文件中，则不应有任何建议。

这个问题最好的数据结构是什么。
我知道我们可以构建一个 trie，但是我们可能只能在用户键入 com 时建议 computer。

感谢任何帮助。

Answer 1

准备:

1. 读取文本文件的所有行作为字符串数组
2. 按字典序对这个数组进行排序

查询:

1. 获取 lower bound给定输入字符串的索引:first
2. 将输入字符串的最后一个字符的值增加 1(如果不是最大值)并得到 lower bound索引，last，对于这个新的输入字符串。如果您的最后一个字符不能递增，请使用数组末尾后的索引。

所有可能的建议都在这两个边界之间的排序数组中不包括最后一个索引:[first, last)。

如果建议太多，可以只建议最短的3条建议进行过滤，或者按统计频率排序。

您也可以打印建议的数量而不是建议它们。类似于谷歌告诉你有多少页面匹配你的查询的方式。然后仅当您的 UI 可以管理匹配数量时才建议字符串。