Search code examples
javasearchsetprefix

Finding entries in a Set containing a prefix

I'm doing a couple of exercises as a Java beginner and I just can't get this to work.

This is what I'm working with:

public static Set<Person> prefixName(final Set<Person> persons, final String prefix) {
    ...
}

The Set consists of names, while the prefix is a substring of a name (or not). So with persons = {Larry, Dave, Laura}, prefix = La, the method would return {Larry, Laura}

I asked a buddy of mine for some help and he said to look into streams. Since the book I'm working with hasn't made any mentions of streams yet, I believe there is an easier and more beginner-friendler solution to it, too!

This is basically the same problem, but with a TreeSet, which apparently has a pretty handy method for exactly this.

Solution

  • A general set can not take advantage of knowing a prefix in order to find elements. You will need to traverse the whole set and check each entry.

    A TreeSet however can take advantage of that knowledge as entries there are sorted by their prefixes. In order to find all prefixes you just need to take the whole sub-tree rooted at the prefix, this can be computed fast.

    Here is an illustration showing the internal structure of a TreeSet:

    TreeSet structure

    Here is the obvious naive implementation:

    public static Set<Person> prefixName(final Set<Person> persons, final String prefix) {
    final Set<Person> personsWithPrefix = new HashSet<>();
    for (final Person person : persons) {
        if (person.getName().startsWith(prefix)) {
            personsWithPrefix.add(person);
        }
    }
    return personsWithPrefix;
}

    Or alternatively a more compact Java 8 solution using streams:

    public static Set<Person> prefixName(final Set<Person> persons, final String prefix) {
    return persons.stream()
        .filter(person -> person.getName().startsWith(prefix))
        .collect(Collectors.toSet());
}