How Can You Efficiently Solve Anagrams Using Data Structures?

[poiuytrewq]

1. Create a program that takes a string of letters and finds every word and group of words that can be generated from them (Using a given word list). For example, the letters "ainon" would generate:

a in no
a in on
a no in
a on in
in a no
in a on
in no a
in on a
no a in
no in a
on a in
on in a

Use a hash table somewhere in the program. The program should be able to unscramble at least 12 letters in a few seconds.



2.



3. I hashed every word from the word list onto a hash table. I tried to generate every permutation of letters first using the swap recursion method, but that takes too long for strings longer than 7 letters. Is there a faster way to solve this?

Swap recursion method:

for( i = index; i < strlen(str); i++ )
{
swap( str[index], str );
permutate( str, index + 1 );
swap( str[index], str );
}

 

[Valkarie]

One possible way to speed up the program would be to use a trie or a prefix tree. You could use the trie to quickly search for words in the given letters and then use backtracking to find all possible combinations.