Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding anagrams for a given word

Two words are anagrams if one of them has exactly same characters as that of the another word.

Example : Anagram & Nagaram are anagrams (case-insensitive).

Now there are many questions similar to this . A couple of approaches to find whether two strings are anagrams are :

1) Sort the strings and compare them.

2) Create a frequency map for these strings and check if they are the same or not.

But in this case , we are given with a word (for the sake of simplicity let us assume a single word only and it will have single word anagrams only) and we need to find anagrams for that.

Solution which I have in mind is that , we can generate all permutations for the word and check which of these words exist in the dictionary . But clearly , this is highly inefficient. Yes , the dictionary is available too.

So what alternatives do we have here ?

I also read in a similar thread that something can be done using Tries but the person didn't explain as to what the algorithm was and why did we use a Trie in first place , just an implementation was provided that too in Python or Ruby. So that wasn't really helpful which is why I have created this new thread. If someone wants to share their implementation (other than C,C++ or Java) then kindly explain it too.

like image 714
h4ck3d Avatar asked Sep 18 '12 12:09

h4ck3d


People also ask

Is there an anagram generator?

Anagram Solver is a tool used to help players rearrange letters to generate all the possible words from them. You input the letters, and Anagram Maker gives you the edge to win Scrabble, Words With Friends, or any other word game.


Video Answer


1 Answers

Example algorithm:

Open dictionary Create empty hashmap H For each word in dictionary:   Create a key that is the word's letters sorted alphabetically (and forced to one case)   Add the word to the list of words accessed by the hash key in H 

To check for all anagrams of a given word:

Create a key that is the letters of the word, sorted (and forced to one case) Look up that key in H You now have a list of all anagrams 

Relatively fast to build, blazingly fast on look-up.

like image 131
Vatine Avatar answered Sep 20 '22 00:09

Vatine