How to check if two String are Anagram of each other - Coding Problem

Here is a Java program to check if two String is an anagram of each other or not.  Two String is said to be an anagram of each other, if they contain exactly the same characters but in a different order. For example "army" and "mary" is an anagram of each other because they contain exact same characters 'a', 'r', 'm' and  'y'. For the sake of simplicity, you can also assume that your solution need not be case-sensitive, which means both ARMY and mary can be matched as an anagram of each other.





import java.util.Arrays;



/**

* Java Program to check if two String is an anagram of each other or not. Two

* String is said to be an anagram of each other, if they contain exactly same

* characters but in a different order. For example "army" and "mary" are anagram

* of each other because they contain exact same characters 'a', 'r', 'm' and

* 'y'.

*

* @author javinpaul

*/

public class Testing {



    public static void main(String args[]) {



        String[][] data = {{"army", "mary"}, {"stop", "tops"}, {"soap", "abcd"}};

        System.out.println("======== Testing areAnagrams() method =======");

        for (String[] value : data) {

            String s1 = value[0];

            String s2 = value[1];

            System.out.printf("Are %s and %s are Anagrams? %b%n", s1, s2,
                       areAnagrams(s1, s2));

        }



        System.out.println("======== Testing isAnagaram() method =======");

        for (String[] value : data) {

            String s1 = value[0];

            String s2 = value[1];

            System.out.printf("Does %s and %s are Anagrams? %b%n", s1, s2, 
                               isAnagram(s1, s2));

        }



    }



    /*

     * One of the easiest way to check if two Strings are an anagram of each other

     * is to take their character array, sort them and check if they are equal.

     * If sorted character arrays are equal then both String are an anagram of

     * each other.

     */

    public static boolean areAnagrams(String first, String second) {

        char[] fa = first.toCharArray();

        char[] sa = second.toCharArray();



        // sort arrays

        Arrays.sort(fa);

        Arrays.sort(sa);



        // check if arrays are equal

        if (Arrays.equals(fa, sa)) {

            return true;

        }



        return false;

    }



    /*

     * Earlier method was using a couple of library methods, which is not permitted during

     * interviews. This method checks if two Strings are anagram without using any utility

     * method. This solution assumes that both source and target string are ASCII strings.

     */

    public static boolean isAnagram(String source, String target) {

        if ((source == null || target == null) || source.length() != target.length()) {

            return false;

        }



        int[] table = new int[256];



        int numOfUniqueCharInSource = 0;

        int numOfCharProcessedInTarget = 0;



        char[] characters = source.toCharArray();



        // store count of each unique character in source String

        for (char ch : characters) {

            if (table[ch] == 0) {

                ++numOfUniqueCharInSource;

            }

            ++table[ch];

        }



        for (int i = 0; i < target.length(); ++i) {

            int c = target.charAt(i);

            if (table[c] == 0) {

                return false;

            }

            --table[c];

            if (table[c] == 0) {

                ++numOfCharProcessedInTarget;

                if (numOfCharProcessedInTarget == numOfUniqueCharInSource) {

                   // its a match if t has been processed completely

                    return i == target.length() - 1;

                }

            }

        }

        return false;



    }



}



Output

======== Testing areAnagrams() method =======

Are army and mary are Anagrams? true

Are stop and tops are Anagrams? true

Are soap and abcd are Anagrams? false

======== Testing isAnagaram() method =======

Does army and mary are Anagrams? true

Does stop and tops are Anagrams? true

Does soap and abcd are Anagrams? false


That's all about how to check if two String is Anagram of each other or not. If you need more String based coding problems for practice then you can also solve problems listed below.  It's an interesting problem and there are a couple of invariants as well as the case-sensitive one I discussed in the first paragraph. You may also be asked to calculate the time and space complexity of this problem, can you calculate?

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Introduction to Algorithms by Thomas H. Corman


More String Problems to solve
If you are interested in solving more String based algorithm problems then here is the list of some of the frequently asked questions.
  • How to Print duplicate characters from String? (solution)
  • How to check if two Strings are anagrams of each other? (solution)
  • How to program to print first non-repeated character from String? (solution)
  • How to reverse String in Java using Iteration and Recursion? (solution)
  • How to check if a String contains only digits?  (solution)
  • How to find duplicate characters in a String? (solution)
  • How to count the number of vowels and consonants in a String? (solution)
  • How to count the occurrence of a given character in String? (solution)
  • How to convert numeric String to an int? (solution)
  • How to find all permutations of String? (solution)
  • 10 Algorithms Courses to Crack Programming Job Interviews (courses)
  • How to reverse words in a sentence without using a library method? (solution)
  • How to check if String is Palindrome? (solution)
  • How to return highest occurred character in a String? (solution)
  • How to reverse a String in place in Java? (solution)
  • 50+ Data Structure and Algorithms Interview Questions (questions)
Thanks for reading this coding interview question so far. If you like this String interview question then please share with your friends and colleagues. If you have any question or feedback then please drop a comment.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check this list of Free Data Structure and Algorithms Courses for Programmers.

No comments:

Post a Comment