Anagram Solver is one of the most common algorithm which is asked in the interview of the Top most companies like Goldman sachs , Facebook . So let us understand Anagram solver in detail.
An Anagram is a word in the English language whose letters has been scrambled . An example is the Anagram 'ehlol' , whose solution is the word 'hello' . So in other words , we need to use all the original given letters exactly once , to produce a meaningful word (exists in Dictionary *here words.txt *) .
An anagram solver will recursively generate the permutations of a given program. A permutation is a reordering of the letters in the word . As it generates the permutations , it will run a search algorithm to see if the permutation is a word in the English language (or in Dictionary) .
Read Also :Find all possible Combination of String in Java
To check if the word exists in the English language, we will need a list of real words. A file containing a sorted list of relevant words will be provided in words.txt . These words will be stored in a class that implements the Dictionary abstract class . Dictionary has an abstract method called contains that accepts a String parameter and returns a boolean. We will use to measure average lookup time, which is the average time it takes the contains method to look up a particular word in the dictionary.
We can create three classes that extend Dictionary:
* LinearDictionary - Searches linearly for words.
* BinaryDictionary - Uses binary search to find words.
* HashDictionary - Stores words in a Hashtable for quick retrieval.
The command line arguments for AnagramSolver.java class are as follows:
AnagramSolver < anagram > < dictionary file > < dictionary type >
Where dictionary type can be l, b, or h for linear, binary, and hash respectively.
Here in the below program we pass the following arguments at the run time
java AnagramSolver oozlyog words.txt b

In the above mentioned search types , HashDictionary search is the best to check the word in the English language(here words.txt) . Linear dictionary is the worst among three .
Read Also : Count total number of times each alphabet appears in the string
Pseudo code :
* Select the search method , that is , linear,binary or hash search as well as pass the Original/input word
at run time .
* Find the all possible permutations of original/input word , pass each unique permuted word to the
chosen search dictionary method .
* If the word passed to the search method is found in the dictionary then print the found word
else
keep find the permutaions of the word and check with the words in the dictionary
Please write in comments if you have any doubts
Demo :


Code :