CODEWITHSUNDEEP
javascriptalgorithmfull-text-searchanagram
juicejonjon
juicejonjon

Reputation: 31

JavaScript algorithm to match words in a dictionary

I have an array that contains a few thousand words. I have an input field on my webpage that allows a user to enter in a couple of letters, and then hit search. When the user hits search, the application should look in the dictionary and see what words can be formed off of the supplied letters. Each letter can be used only once ( like in scrabble ).

Is there already a search library for doing something like this? I don't want to reinvent the wheel if not necessary. If not, does anyone have ideas for a high performance solution. I'd imagine this has been done millions of times before.

Upvotes: 3

Views: 3365

Answers (3)

Ioan Alexandru Cucu
Ioan Alexandru Cucu

Reputation: 12269

What you need to do is convert the array of words in a hashtable where the key is each word's letters sorted. Ex:

['car', 'shoe', 'train']
=> {'acr': ['car'],
     'ehos': ['shoe'],
     'ainrt': ['train']}

Then you take the user's letters, you sort them, and you do a hashtable (any dictionary impl would do, but hashtables are most efficient in this case) lookup using the sorted letters as key. The list corresponding to your key is the list of words you can do with those letters. This has the advantage of having a time complexity of O(n) = 1.

Upvotes: 1

Juan-Carlos
Juan-Carlos

Reputation: 31

Steve Hanov wrote something about this too:

http://stevehanov.ca/blog/index.php?id=120

Upvotes: 1

duffymo
duffymo

Reputation: 308783

John Resig of jQuery fame has been thinking about this problem as well:

http://ejohn.org/blog/dictionary-lookups-in-javascript/

Upvotes: 1

Related Questions