我有一个很大的字符串列表，需要由 iPhone/Android 应用程序的用户搜索。字符串按字母顺序排序，但这实际上并不是那么有用，因为如果搜索查询落在字符串内的任何位置，而不仅仅是开头，则字符串应该包含在结果中。当用户输入他们的搜索查询时，应该更新搜索以反射(reflect)他们当前输入的结果。 (例如，如果他们键入“cat”，它应该在他们键入时显示“c”、“ca”和“cat”的结果)。
我目前的做法如下:
我有一堆“搜索结果”，一开始是空的。如果用户键入某些内容使搜索查询更长，我将当前搜索结果压入堆栈，然后仅搜索当前搜索结果以寻找新的(不可能出现在完整字符串列表中但不在当前搜索结果中的内容)在这种情况下的结果)。
如果用户按下退格键，我只需要将搜索结果从堆栈中弹出并恢复它们。这几乎可以立即完成。
这种方法非常适合“向后”搜索(使搜索查询更短)以及搜索查询已经足够长以致结果数量较少的情况。但是，对于用户键入的前几个字母中的每一个，它仍然需要在 O(n) 时间内搜索整个字符串列表，这非常慢。
我考虑过的一种方法是预先编译所有可能的 2 或 3 个字母搜索查询的结果列表。这种方法的问题是它需要 26^2 或 26^3 个这样的列表，并且会占用相当大的空间。
您能想到任何其他优化或替代方法吗？
最佳答案
您应该考虑使用 prefix tree (trie)制作一个预先计算好的列表。我不确定以子字符为基础显示“c”、“ca”和“cat”的结果是个好主意。例如，假设用户正在搜索“吃”这个词。您的算法必须找到所有包含“e”的单词，然后是“ea”，最后是“eat”；其中大部分对用户没有用。对于电话应用程序，如果您以单词为基础进行操作可能会更好。多词字符串可以标记化，因此在“大量股份”中搜索“股份”可以正常工作，但不能搜索“take”。
关于string - 高效搜索大量字符串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10421649/