Sulot Sulot - 2 years ago 67
Javascript Question

How to check if a permutation (or part) of a string is in list (dictionary)?

I programming a simple search app for Scrabble. Find all possible words from a string.
Permutation part is done. I've created a function Permute(string) that output an array with all permutation.

var dictionary=["abc","abcd",ab","dhgd","adbft"];

var input="abcd";

Now, I have to check if words exist. Should I try all length? Is there another more efficient way?

//Check all the item of the output array
for(var i=0; i<output.length;i++){
//Check if all length of output
for(var j=2;j<output[i].length;i++)
//Check all these possibilities if they exist in the dictionary
for(word in dictionary){


I can't really imagine how long it would be if the dictionary is 250 000 words... Is there a better way?

Joe Joe
Answer Source

The first thing to check with anagrams is the length. If you dictionary is only for checking if the permutation exists then I would create a structure with length as a first dimension. e.g.

dictionary = {1: ['a', 'i'], ... 3: ['cat', 'dog', 'too']}

This is easy to do.

Next, permutations aren't the most efficient way to check for anagrams. You could, for example, sort the characters and them compare:

 dictionary = {1: ['a', 'i'], ... 3: ['act', 'dgo', 'oot']}

Then you can sort the characters your query string and do a direct comparison. This cuts out a huge chunk of permutations.

Then you should reconsider using a linear structure for your dictionary. Something hash-based works much better. Why not use the built-in dictionary in Javascript.

dictionary = {1: {'a': ['a'], 'i': ['i']}, ... 3: {'act': ['cat', 'cat'], 'dgo': ['dog'], 'oot': ['too']}}

This maps the sorted string to the possible strings that are anagrams.

Then to find your potential words you just look up dictionary[myword.length][sort_string(myword)]

Your sort function is:

function sort_string(input) {
    return input.split("").sort().join("")}

The resulting complexity will be O(1)ish (one step to calculate the length, one step to sort the letters, one step to look up first level, one step to hash and look up second level). It doesn't slow down as the dictionary increases.

Your original was O(n), i.e. searching the dictionary for as many words as exist, and the speed depends how big your dictionary is.

If you want to search for possible available words, then you're going to want to create ngrams and search for those. Decide what's the minimum word length and the maximum word length, then create windows of that length. This would require creating permutations and at this point you get into more interesting algorithms like search trees, back-tracking etc. I suggest a read of the relevant Wikipedia articles.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download