1

问题：我们得到一个包含多行文本的文本文件。现在用户将输入几个字母，我们必须根据给定文件中的文本给出自动完成建议。假设文件包含computer science is fun. computer engineering is awesome. 现在，如果用户类型com我们需要提供建议computer science和computer engineering. 如果用户键入is建议应该是funand awesome。用户可以输入文本文件中可能存在或不存在的任何单词。如果该词不在文件中，则不应有任何建议。

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

感谢任何帮助。

4

1 回答 1

1

准备：

  1. 将文本文件的所有行作为字符串数组读取
  2. 按字典顺序排序此数组

询问：

  1. 获取给定输入字符串的下限索引：first
  2. 将输入字符串的最后一个字符的值增加 1（如果不是最大值），并获取此新输入字符串的下限索引。last如果您的最后一个字符不能递增，请使用数组末尾之后的索引。

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

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

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

于 2016-04-05T09:04:25.613 回答