在List.contains(String)的情况下部分匹配字符串
我有一个List
List list = new ArrayList(); 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个字符串。 还有什么其他(更快)的方法呢?
谢谢。
如果Roadrunner-EX的建议还不够,我相信您正在寻找Knuth-Morris-Pratt算法 。
时间复杂度:
- 表算法的时间复杂度为O(n),预处理时间
- 搜索算法的时间复杂度为O(k)
因此,整个算法的复杂性是O(n + k)。
- n =列表的大小
- k =您要搜索的模式的长度
正常的蛮力将具有O(nm)的时间复杂度
此外,对于使用相同搜索字符串进行搜索,KMP算法将采用相同的O(k)复杂度,另一方面,对于powershell逼近方法,它将始终为O(km)。
也许您想将每个String组放入一个HashSet中,而且通过片段,我的意思是不要添加“IJ KL”,而是分别添加“IJ”和“KL”。 如果您同时需要列表和此搜索function,则可能需要维护两个集合。
作为第二个答案,在重新阅读您的问题时,您还可以从接口List
inheritance,仅将其专门用于Strings
,并覆盖contains()方法。
public class PartialStringList extends ArrayList { public boolean contains(Object o) { if(!(o instanceof String)) { return false; } String s = (String)o; Iterator iter = iterator(); while(iter.hasNext()) { String iStr = iter.next(); if (iStr.contain(s)) { return true; } } return false; } }
从你之前的评论来看,这可能不是你想要的速度,但这更符合你的要求吗?
您可以使用Apache Commons Collections中的 IterableUtils 。
List list = new ArrayList (); list.add("ABCD"); list.add("EFGH"); list.add("IJ KL"); list.add("M NOP"); list.add("UVW X"); boolean hasString = IterableUtils.contains(list, "IJ", new Equator () { @Override public boolean equate(String o1, String o2) { return o2.contains(o1); } @Override public int hash(String o) { return o.hashCode(); } }); System.out.println(hasString); // true
您可以遍历列表,然后在每个String上调用contains()。
public boolean listContainsString(List list. String checkStr) { Iterator iter = list.iterator(); while(iter.hasNext()) { String s = iter.next(); if (s.contain(checkStr)) { return true; } } return false; }
我认为,这样的事情应该有用。
怎么样:
java.util.List list = new java.util.ArrayList (); list.add("ABCD"); list.add("EFGH"); list.add("IJ KL"); list.add("M NOP"); list.add("UVW X"); java.util.regex.Pattern p = java.util.regex.Pattern.compile("IJ"); java.util.regex.Matcher m = p.matcher(""); for(String s : list) { m.reset(s); if(m.find()) System.out.println("Partially Matched"); }
如果在目标字符串中找不到任何测试字符串,则使用正则表达式来快速执行内部循环。
public static void main(String[] args) throws Exception { List haystack = Arrays.asList(new String[] { "ABCD", "EFGH", "IJ KL", "M NOP", "UVW X" }); List needles = Arrays.asList(new String[] { "IJ", "NOP" }); // To cut down on iterations, create one big regex to check the whole haystack StringBuilder sb = new StringBuilder(); sb.append(".*("); for (String needle : needles) { sb.append(needle).append('|'); } sb.replace(sb.length() - 1, sb.length(), ").*"); String regex = sb.toString(); for (String target : haystack) { if (!target.matches(regex)) { System.out.println("Skipping " + target); continue; } for (String needle : needles) { if (target.contains(needle)) { System.out.println(target + " contains " + needle); } } } }
输出:
Skipping ABCD Skipping EFGH IJ KL contains IJ M NOP contains NOP Skipping UVW X
如果你真的想变得可爱,你可以使用二分搜索来识别目标列表的哪些段匹配,但它可能不值得。
这取决于你发现命中的可能性。 低命中率将带来良好的结果。 高命中率将比简单的嵌套循环版本好很多。 如果某些针击中许多目标,则考虑反转环,而其他针没有击中。
这一切都是为了尽快中止搜索路径。
是的你可以! 有点。
你在寻找什么,通常被称为模糊搜索或近似字符串匹配 ,这个问题有几种解决方案。
例如,使用FuzzyWuzzy lib,您可以根据它们与特定搜索词的相似程度为所有字符串分配一个分数。 实际值似乎是与搜索字符串长度匹配的字符数的整数百分比。
在调用FuzzySearch.extractAll
,您可以决定将字符串视为匹配的最低分数。
还有其他类似的库值得一试,比如google-diff-match-patch或Apache Commons Text Similarity API等等。
如果你需要一些非常重的东西,最好的选择可能是Lucene ( Ryan Shillington也提到过)