How to find String Anagrams

0
1240

Quite often interviewers just give a coding question to solve some of the standard questions. Finding out String Anagrams is one among them which gets covered by lot many and at different level interview positions.

Popular Java Coding Interview Questions – Finding out if two String are Anagrams

In my last post I started discussing about the Java Programming Interview questions and found the solution for a popular one: ‘How to find out Armstrong Numbers’ and provided the source code as well.

In continuation to that, today I am going to discuss about another quite common, tricky but a simple coding interview question:
Find out if two given strings are anagrams or not.

Find out Anagrams

In addition to that, we will also have a look at a recursive method used to generate all the permutations of a given string. This at times, can be further implemented to validate the generated words in a dictionary, if provided.

Coming to the simple definition first: “An anagram is a word, name or phrase formed by rearranging the letters of another, using each original letter only once.” You can think of it like taking one word and then just scrambling the letters to get another word.

Some examples of valid and interesting anagrams:

New York Times: monkeys write
Evangelist: evil's agent
Clint Eastwood: Old West action 
Arnold Schwarzenegger: he’s grown large n’ crazed
Britney Spears: best PR in years
Dormitory: dirty room

 

Example of words which are NOT anagrams:

Wed -> Weed (doesn't have the exact same number of letters)

Being-> Begins (one word is longer than the other)

So now we are going to perform two tasks here with the help of Java code:

1)            Generate all the possible permutations of a given word
2)            Find out if two words are Anagrams of each other or not
Let’s have a look at the code below and I will explain further after that:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/**
 * A simple Java program to find out if given two strings 
 * are Anagrams of each other or not.  Example:
 * Dormitory: dirty room
 * New York Times: monkeys write
 * 
 * This program will also generate all the possible permutations
 * of a given String.
 */

import java.util.Arrays;
import java.util.Locale;
import java.util.Scanner;

/**
 * @author Shalini Goyal
 */
public class DiscoverAnagram {

 public static void main(String[] args) {
     
        System.out.print("Lets check if two Strings are Anagrams.\nFirst One: ");
        Scanner scannerOne = new Scanner(System.in);
        String stringOne = scannerOne.nextLine();
        
        System.out.print("Enter Second One: ");
        Scanner scannerTwo = new Scanner(System.in);
        String stringTwo = scannerTwo.nextLine();
        
        //Call to check if two strings are anagrams
        if(isAnagram(stringOne, stringTwo)){
         System.out.println("Yes, Both the strings are Anagrams !!!");
        }else{
         System.out.println("No, Both the strings are NOT Anagrams !!!");
        }
        
      //Generate the anagrams for a given string
  Scanner input = new Scanner(System.in);
        System.out.print("Enter String to generate Anagrams: ");
        String chars = input.next();
        
        System.out.print("All the possible Permutations for "+ chars + ": ");
        //Create all possible combinations
        createAllPermutations("", chars);
 }
 
 /**
  * Method to check and compare two strings if they are anagram
  * @param firstWord
  * @param secondWord
  * @return boolean
  */
 public static boolean isAnagram(String firstWord, String secondWord) {
  //Lets remove the spaces from in between of each string
  char[] firstWordChars = firstWord.replaceAll("[\\s]", "").
       toUpperCase(Locale.ENGLISH).toCharArray();
  char[] secondWordChars = secondWord.replaceAll("[\\s]", "").
       toUpperCase(Locale.ENGLISH).toCharArray();
  
  Arrays.sort(firstWordChars);
  Arrays.sort(secondWordChars);
  return Arrays.equals(firstWordChars, secondWordChars);
 }

 
 /**
  * Method to create different permutations 
  * @param fixedChar
  * @param chars
  */
  public static void createAllPermutations(String fixedChar, String charsToMove) {
   if (charsToMove.length() <= 1){
    System.out.println(fixedChar + charsToMove);
   }
   else{
    for (int i = 0; i < charsToMove.length(); i++) {
     try {
      String newCharsToMove = charsToMove.substring(0, i)
                + charsToMove.substring(i + 1);
      createAllPermutations(fixedChar + charsToMove.charAt(i), newCharsToMove);
     } catch (Exception e) {
      e.printStackTrace();
      }
    }//End For Loop
   }
 }//End of Method
  
}//End of Class

Task 1 has been achieved very simply by accepting two strings as inputs which may have multiple words even. Then removing all the spaces in between them and making the char array. Both the char arrays are then getting sorted and compared to find if equal or not.

That’s it really!!! There can be many more approaches to solve this. For instance: counting the characters in each word and  matching them for the second one. A Hashmap can be used to store this and where key would be the letter and count would be the key.

Task 2 has been again coded simply but may be tricky to understand as it is using the recursive method calls.

To understand how it works, just take a three letters word ‘Red’.
Now, if you have to generate the different words using the three letters R, E, D, you would just shuffle them around and form the new words.

Now lets say we have five letters word, how will you approach now? You would most probably fix the position of first three letters and shuffle around rest two. Once done, you would fix the position of first two letters and shuffle rest. And at last, you would fix the first letter and shuffle rest.

Once all the words are formed this way, you would like to replace the position of first second and third letter and repeat the entire process. In short, each time you would fix a different letter in the beginning and then make all the possible shuffles.

The very same approach has been followed by the recursive method createAllPermutations. It is fixing the initial letter(s) and then making different combinations out of left out letters in the string.

Previous articleJava for Beginners
Next articleSingleton Bean Vs. Pattern
I have spent almost 10 years playing around Java and related technologies. I love to write on different topics and would be very much willing to hear back your feedback/suggestions on them. This site is a medium to share my knowledge with the Java folks and grow further. My other interests include traveling, driving, swimming and dance. But yes, my web site has become my passion over the time :) I live in Scotland and travel to India often, my roots being there.

NO COMMENTS

LEAVE A REPLY