Fastest way to search a word in a word list?

I have a word list like "English Open Word List" used to create word games. The list is in txt file with space between words, like; aa aah aahed .........and so on. I want to search it while typing the letters in the word, like google suggestions in the search bar. What is the fastest algorithm to do it? In any language?

• You can use a trie. – Yuval Filmus Apr 7 '18 at 17:26

1 Answer

Trie might help, it stores your "word list" like this:

              a
/ \
[a]   a
/      \
[a]       h
\
e
\
[d]


And you can query by some operation like trie['a']['a']['h']['e'], which is just array index operation. It takes large memory but it's very efficient. The complexity of the query operation is $O(n)$, n is the length of the queried string.

• Thanks mate. Trie is the answer. "Google suggestion" was an overshoot. Trie has lookup time of less than ~0.1 ms and I just need about 4 words per second. – Jason Depp Apr 7 '18 at 19:04
• It works best when all words are short but there're tons of words – ice1000 Apr 8 '18 at 1:19