Efficient algorithm for grouping array of strings by prefixes

Question

I wonder what is the best way to group an array of strings according to a list of prefixes (of arbitrary length). For example, if we have this:

prefixes = ['GENERAL', 'COMMON', 'HY-PHE-NATED', 'UNDERSCORED_']

Then

tasks = ['COMMONA', 'COMMONB', 'GENERALA', 'HY-PHE-NATEDA', 'UNDERESCORED_A', 'HY-PHE-NATEDB']

Should be grouped this way:

[['GENERALA'], ['COMMONA', 'COMMONB'], ['HY-PHE-NATEDA', 'HY-PHE-NATEDB'], ['UNDERESCORED_A'] ]

The naïve approach is to loop through all the tasks and inner loop through prefixes (or vice versa, whatever) and test each task for each prefix.

Can one give me a hint how to make this in a more efficient way?

Answer 1

There are a few options, but you might be interested in looking into the trie data structure. http://en.wikipedia.org/wiki/Trie

The trie data structure is easy to understand and implement and works well for this type of problem. If you find that this works for your situation you can also look at Patricia Tries which achieve the similar performance characteristics but typically have better memory utilization. They are a little more involved to implement but not overly complex.