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";
output=Permute(input);
//result:
0:"abcd"
1:"abdc"
2:"acbd"
3:"acdb"
...etc
``````

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){
output[i].substring[1:j]==dictionary[word];
}

}};
``````

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

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)]`

``````function sort_string(input) {