Fastest way to find substring in JAVA

Question

lets say i have list of names.

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

and this list contains few thousands nameslist in it. What is the fastes way to know that this list contains names start with given name.

String name = "jon"

result should be 2.

I have tried with comparing every element of list with substring function (it works but) it is very slow specially when list is huge.

Thanks is advance.

Answer 1

You could use a TreeSet for O(log n) access and write something like:

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);

which prints 2 as you expect.

Alternatively, you could use Set<String> subset = set.subSet("jon", "joo"); to return the full list of al names that start with "jon", but you need to give the first invalid entry that follows the jons (in this case: "joo").

Answer 2

Have a look at Trie. It's a data structure aimed to perform fast searches according to word prefixes. You may need to manipulate it a bit in order to get the number of leafs in the subtree, but in any case you do not traverse the entire list.