How to check if a string contains an element of a string array?

Question

I'd like to to check if a string contains an element from a String array. I think that iterating all the array elements and seeing if String.contains(an element) does not seem to efficient. So I wonder if there's a more efficient way to make this look-up fast.

For example, I want to get the country name from an address string. Users can write their address without any constraints. The address string can contain the country name or city name. So I want to see if the address string has an element from an array that I will build has a bunch of country names and city names.

My current solution is:

 ArrayList<String> list;
 String address;
            ...
    for (String s : list) {
        if (address.contains(s))
            return s;
    }

This is O(n). I wonder if there's a faster solution.

Answer 1

I assume you are not using Guava or another library with a join method. In that case, you can build a regular expression by hand.

private String regex(String[] names) {
    final StringBuilder b = new StringBuilder();
    String separator = "";
    for (final String name: names) {
        b.append(separator);
        b.append(Pattern.quote(name));
        separator = "|";
    }
    return b.toString();
}

The loop and the separator variable is the "no-if" way to join the names. The quote call ensures that characters like $, [, or . do not mess things up. What if one of your strings were "St. Louis"?

Then, you use Matcher.find to check.

public boolean contains(String target, String[] names) {
    String regex = regex(names);
    Pattern pattern = Pattern.compile(regex); // Fixed, as per @Java Devil's comment.
    Matcher m = pattern.match(target);
    return m.find();
}

If you want to capture the matched string, enclose the regex in parentheses, and return m.group(1) instead.

Answer 2

You can use a for-loop to iterate through the array and check if the elements are in the String.

A better way to check if a String includes a certain string is to use the methods in the String class, such as String.contains(char). You should do some more experimenting before asking a trivial question, or at least give us some examples that can be solved directly.