Anagram Solver ( Jumbled words to find a meaningful Dictionary word ) : Java Program

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 :


anagram solver java program














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



About The Author

Subham Mittal has worked in Oracle for 3 years .
For more java articles ,Click here to Subscribe JavaHungry