这在某种程度上取决于您要搜索的项目数量。如果列表相对较小，您可以执行以下操作string.contains检查一切。因此，当用户输入“A”时，您将搜索整个列表：
for each contact in contacts
if contact.Name.Contains("A")
Add contact to results
然后用户输入“T”，你依次搜索之前返回的结果：
for each contact in results
if contact.Name.Contains("AT")
Add contact to new search results
如果联系人列表很大，事情会变得更有趣，但对于手机中通常拥有的联系人数量（一千个就很多了！），这将非常有效。
如果面试官说“使用之前搜索的结果进行新的搜索”，那么我怀疑这就是他正在寻找的答案。创建新的后缀树比顺序搜索先前的结果集需要更长的时间。
您可以通过将子字符串的位置与联系人一起存储来对此进行优化，以便下次您要做的就是检查下一个字符是否符合预期，但这样做会使算法有点复杂（您必须将第一次搜索视为特殊情况，并且必须显式检查字符串长度等），并且在前几个字符之后不太可能提供太多好处，因为要搜索的列表的大小会非常小。纯顺序搜索contains检查速度会很快。用户不会注意到通过优化节省的几微秒。
编辑问题后更新
如果您想对一百万个联系人执行此操作，顺序搜索可能不是一开始的最佳方法。虽然我还是想尝试一下。 “足够快，可容纳一百万次联系人”提出了“足够快”究竟意味着什么的问题。在 100 万个联系人中搜索是否存在单个字母需要多长时间？用户愿意等待多长时间？还要记住，您只需show用户执行另一操作之前的一页联系人。您几乎可以肯定在用户按下第二个键之前就可以做到这一点。特别是如果您有一个后台线程执行搜索，而前台线程处理输入并将匹配字符串的第一页写入显示。
无论如何，您可以通过创建二元索引来加快初始搜索速度。也就是说，对于每个二元组（两个字符的序列），构建包含该二元组的名称列表。您还需要为每个字符创建一个字符串列表。因此，根据您的姓名列表，您将拥有：
r - ram
a - ram, feat, eat, a
m - ram
h - hello, hi
...
ra - ram
am - ram
...
at - feat, eat, at
...
etc.
我想你应该已经明白了。
该二元索引存储在字典或哈希图中。英语中只有 325 个可能的二元组，当然还有 26 个字母，所以你的字典最多有 351 个条目。
因此，您几乎可以立即查找 1 个字符和 2 个字符的名称。这对你有什么帮助？
古腾堡计划文本分析 http://www3.nd.edu/~busiforc/handouts/cryptography/Letter%20Frequencies.html表明英语中最常见的二元组仅出现 3.8% 的时间。我意识到名字不会完全共享这个分布，但这是一个相当不错的粗略数字。因此，在输入前两个字符后，您可能会使用列表中不到 5% 的名称。一百万的百分之五就是五万。只需 50,000 个名称，您就可以开始使用我最初描述的顺序搜索算法。
这种新结构的成本并不算太糟糕，尽管它足够昂贵，无论如何我肯定会首先尝试简单的顺序搜索。在最坏的情况下，这将导致您额外花费 200 万次对名称的引用。如果您构建一个 2 级 trie 而不是字典，则可以将其减少到一百万个额外引用。那需要slightly查找和显示单字符搜索结果的时间较长，但不足以引起用户的注意。
这种结构也很容易更新。要添加名称，只需浏览字符串并输入适当的字符和二元组即可。要删除名称，请通过提取二元组的名称，然后从二元组索引中的相应列表中删除该名称。
