3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You can use a trie. $\endgroup$ – Yuval Filmus Apr 7 '18 at 17:26
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jason Depp Apr 7 '18 at 19:04
  • $\begingroup$ It works best when all words are short but there're tons of words $\endgroup$ – ice1000 Apr 8 '18 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.