java - 在Java中从ArrayList中搜索包含特定字符串的一组字符串

Question

是否有任何快速算法可以在字符串数组列表中搜索特定字符串？

例如:

我有一个数组列表:

{"white house","yellow house","black door","house in heaven","wife"}

并且想要搜索包含“house”的字符串。它应该在最短的时间内返回 {"white house","yellow house","house in heaven"}。我的意思是我的问题是处理没有索引的大数据(大约 167000 个字符串的列表)。

谢谢!

Answer 1

您的问题有两个答案，具体取决于您是否计划运行多个查询:

• 如果您只需要运行一次查询，那么您就不走运了:您必须从头到尾搜索整个数组。
• 如果您需要运行大量查询，可以通过构建索引来减少工作量。

制作一个数据结构Map<String,List<String>> ，浏览 List<String> 中的字符串，并将它们拆分成单词。对于标记列表中的每个单词，将原始字符串添加到相应的列表中。

此操作在 O(N*W) 中运行，其中N是长字符串的数量，W是每个字符串的平均单词数。有了这样的 map ，您可以在 O(1) 中运行查询.

请注意，只有当查询数量显着超过每个字符串中的平均单词数时，此方法才有效。例如，如果您的字符串平均有十个单词，并且您需要运行五到八个查询，则线性搜索会更快。