HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Fastest way to search a word in a word list?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
searchwaywordfastestlist

Problem

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?

Solution

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.

Code Snippets

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

Context

StackExchange Computer Science Q#90348, answer score: 5

Revisions (0)

No revisions yet.