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

2022-09-02 10:45:35

我有一个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")truelist.contains("IJ")

我有一个包含15000个字符串的列表。我必须检查大约10000个字符串,如果它们存在于列表中。还有什么其他(更快)的方法可以做到这一点?

谢谢。


答案 1

如果Roadrunner-EX的建议还不够,那么我相信你正在寻找Knuth-Morris-Pratt算法

时间复杂度:

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

因此,整体算法的复杂性为O(n + k)。

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

普通蛮力的时间复杂度为O(nm)

此外,KMP算法将采用相同的O(k)复杂性进行相同的搜索字符串,另一方面,对于蛮力方法,它将始终是O(km)。


答案 2

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