在List.contains(String)的情况下部分匹配字符串

Question

我有一个 List<String>

List<String> list = new ArrayList<String>();
list.add("ABCD");
list.add("EFGH");
list.add("IJ KL");
list.add("M NOP");
list.add("UVW X");

如果我这样做list.contains("EFGH"),它会返回true.我可以获得真实情况list.contains("IJ")吗？我的意思是,我可以部分匹配字符串以查找它们是否存在于列表中？

我有一个15000字符串的列表.如果它们存在于列表中,我必须检查大约10000个字符串.还有什么其他(更快)的方法呢？

谢谢.

Answer 1

如果Roadrunner-EX的建议不够,我相信您正在寻找Knuth-Morris-Pratt算法.

时间复杂度:

• 表算法的时间复杂度为O(n),预处理时间
• 搜索算法的时间复杂度为O(k)

因此,整个算法的复杂性是O(n + k).

• n =列表的大小
• k =您要搜索的模式的长度

正常蛮力的时间复杂度为O(nm)

此外,对于使用相同搜索字符串进行搜索,KMP算法将采用相同的O(k)复杂度,另一方面,对于强力接近,它将始终为O(km).

Answer 2

也许您想将每个字符串组放入一个 HashSet 中，通过片段，我的意思是不要添加“IJ KL”，而是分别添加“IJ”和“KL”。如果您同时需要列表和此搜索功能，则可能需要维护两个集合。