How to use Trie to do partial autocomplete

user_7863646 0
Viewed 558

Given a large list of words (say 1 million). Using Trie, we could easily implement prefix match. But how can I implement partial match.

For example we have a list of words {"abc", "def", "lunch", "diner"....}, how I can get lunch when searching "unc" ?

Is Trie still a good data structure to use in this case? What are the possible ways to implement it efficiently?

partial trie match java string
1 Answers

The most common structure used for this sort of application is a Suffix Tree This is really a version of a Trie that allows all the suffixes for a string to be stored efficiently in a single structure. There are other options but this is a good balance between efficiency and simplicity.

user_37051270
Related