在JAVA中查找子字符串的最快方法

Question

让我说我有名单.

ArrayList<String> nameslist = new ArrayList<String>();
nameslist.add("jon");
nameslist.add("david");
nameslist.add("davis");
nameslist.add("jonson");

此列表中包含数千个名单.知道此列表包含以给定名称开头的名称的方法是什么.

String name = "jon"

结果应该是2.

我已经尝试将列表的每个元素与子串函数进行比较(它可以工作但是)当列表很大时它非常慢.

谢谢你的提前.

Answer 1

您可以使用TreeSet进行O(log n)访问,并编写如下内容:

TreeSet<String> set = new TreeSet<String>();
set.add("jon");
set.add("david");
set.add("davis");
set.add("jonson");
set.add("henry");

Set<String> subset = set.tailSet("jon");
int count = 0;
for (String s : subset) {
    if (s.startsWith("jon")) count++;
    else break;
}
System.out.println("count = " + count);

它会按照您的预期打印2.

或者,您可以使用Set<String> subset = set.subSet("jon", "joo");返回以...开头的完整名称列表"jon",但是您需要在jons之后给出第一个无效条目(在本例中为"joo").