Quick comparison strings with startsWith

Question

I have the following code:

String[] names = {"aa", ..........., "bb"};
for (int i = 0; i < names.length; i++) {
    if (names[i].toLowerCase().startsWith(query.toLowerCase()))
        c.addRow(new Object[]{i, names[i]});
}

Since the array names can be long, I'm wondering what is the best way to write this code from performance point of view. In this way the loop is O(N). Is there any java data structure to do the same thing in a quicker way?

If `names` is sorted, you can do a binary search for the first correct value and then loop forwards and backwards in the array to find the rest of the matches, and that should be about as efficient as possible — phflack, Nov 10 '15 at 17:46

score 1 · Answer 1 · edited May 23 '17 at 12:03

1

How about a Prefix tree?

refer to:

How to create a simple prefix index in Java?

http://www.toptal.com/java/the-trie-a-neglected-data-structure

edited May 23 '17 at 12:03

Community

1
1

answered Nov 10 '15 at 17:43

柯鴻儀

613
1
10
25

or just sort the array ,then you can find all the items after finding the first items. – 柯鴻儀 Nov 10 '15 at 17:45

Sergey Kalinichenko · Accepted Answer · 2015-11-10T18:12:33.560

You can order the names, use binary search with a case-insensitive comparator to find the insertion spot for the potential prefix, and walk the array to catch all other words with the same prefix:

// At preparation time
Arrays.sort(names, String.CASE_INSENSITIVE_ORDER);
...
// At query time
int pos = Arrays.binarySearch(names, query, String.CASE_INSENSITIVE_ORDER);
if (pos < 0) {
    pos = -(pos+1);
}
while (pos < names.length) {
    if (names[pos].toLowerCase().startsWith(query.toLowerCase())) {
        c.addRow(new Object[]{pos, names[pos]});
        pos++;
    } else {
        break;
    }
}

Arrays.binarySearch finds an insertion point. If the name matches, pos would be non-negative; otherwise, you need to convert it to a valid index with this expression: -(pos+1) If query is a proper prefix, its insertion point would be in front of the first name with a matching prefix. Since names is sorted, all entries with the same prefix would be next to each other. That's why you can walk the list linearly until first mismatch, and stop at that point.

Quick comparison strings with startsWith

2 Answers2