How can I implement a string filter algorithm in iOS that mirrors the contact auto complete in 'Messages'?

Question

In iOS, when you start to type someone's name in to send a new SMS/iMessage etc, an auto complete list pops up.

I am trying to recreate the way this search algorithm works, however it's not as straight forward as you might think. You can try this out on your device to see what I mean, but for example if I type "Joh" or "Brow" then "John Brown" will show up. However typing "ohn" will not show any results. To make it even more difficult, typing in "Mr Green" will allow "Mr Evan Green" to show... try it yourself in messages, it's probably easier to understand that way.

Is there an easy way to implement this autocomplete algorithm? (I have an array of NSStrings containing names, and a substring to filter them with).

If there's no easy way, how would you go about this?

Answer 1

You should create a Trie out of your strings for this purpose. You can also use suffix tree (a improvement over the TRIE) or suffix array (stripped down data structure based on the suffix tree). Check out this link for algorithm using Trie.

Check out this question for difference between these data structures.

Idea of suffix tree is to have path to every suffix of the input string and than you can use tree search to find if a random string is matching the input string very fast.