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

regex java

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 + k）。

普通蛮力的时间复杂度为O（nm）

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

答案 2

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

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