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 :
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 :
public class AnagramSolver { static Dictionary dictionary; String temp=" "; public AnagramSolver(Dictionary d) { this.dictionary=d; } public static String solve(String s) { double before = System.currentTimeMillis(); dictionary.contains(s); double after = System.currentTimeMillis(); if(dictionary.contains(s)) return s; else return null; } public static void main (String args[]) throws Exception { if(args[2].equals("b")) { BinaryDictionary b=new BinaryDictionary(args[1]); // Click here Binary Dictionary code AnagramSolver as=new AnagramSolver(b); } else if (args[2].equals("l")) { LinearDictionary l=new LinearDictionary(args[1]); // Click here Linear Dictionary code AnagramSolver as=new AnagramSolver(l); } else if(args[2].equals("h")) { HashDictionary h=new HashDictionary(args[1]); // Click here Hash Dictionary code AnagramSolver as=new AnagramSolver(h); } permute(args[0]); } public static void permute( String input) { System.out.println("Original/Input word is :" +input); int inputLength = input.length(); boolean[ ] used = new boolean[ inputLength ]; StringBuffer outputString = new StringBuffer(); char[ ] in = input.toCharArray( ); doPermute ( in, outputString, used, inputLength, 0 ); } public static void doPermute ( char[ ] in, StringBuffer outputString, boolean[ ] used, int inputLength, int level) { if( level == inputLength) { String temp=solve(outputString.toString()); if(temp!=null) { System.out.println(""); System.out.println("congratulations!!!! " +temp.toUpperCase()+" is the word in the dictionary"); System.exit(0); } return; } for( int i = 0; i < inputLength; ++i ) { if( used[i] ) continue; outputString.append( in[i] ); used[i] = true; doPermute( in, outputString, used, inputLength, level + 1 ); used[i] = false; outputString.setLength( outputString.length() - 1 ); } } } words.txt a aardvark abaci aback abacus abaft abalone ......... ......... zygotic zymurgy