Tuesday 2 February 2016

Write a function to check whether two strings are anagram of each other.


Input: str1 – “geeksforgeeks”, str2 – “geeksforgeeks”
Output = Strings are Angram

Input: str1 – “geeksforgeeksk”, str2 – “lgeeksforgeeks”
Output = Strings are not Angram

Approach#1:
Sort both the strings and then compare the strings.
Time Complexity: O(nlogn).
package crack.coding.interview;
import java.util.Arrays;
public class AngramSrtings {
     /**
      * Check that the Strings are anagram.
      * @param str1
      * @param str2
      * @return
      */
     private static boolean isStringsAngrmUsingSorting(String str1, String str2) {
           if(str1.length()!= str2.length()) {
                return false;
           }

           char[] array1 = str1.toCharArray();
           char[] array2 = str2.toCharArray();
           Arrays.sort(array1);
           Arrays.sort(array2);
           int len = array1.length;
           for (int i = 0; i < len; i++) {
                if(array1[i]!=array2[i]) {
                     return false;
                }
           }
           return true;
     }

     /**
      * Driver method.
      * @param args
      */
     public static void main(String[] args) {
           String str1 = "geeksforgeeks";
          
           String str2 = "geeksfoeekrgs";
           boolean result = isStringsAngrmUsingSorting(str1,str2);
           String angram = "Not Angram";
           if(result) {
                angram = "Angram";
           }
           System.out.println("Strings are "+angram);
     }
}

Approach#2:
Check if the two strings have same count for each character. It can be achieved using temporary array or HashMap.

1. Create an array of size 256(=all possible character ASCIIs) initialized with 0′s.
2. For first string increment count of character in count array.
3. For second string decrement the count of character from count array.
4. Repeat steps 2 and 3 till we reach end of any string.
5. Check if array contains only zero then strings are anagram otherwise not.

package crack.coding.interview;
import java.util.Arrays;
public class AngramSrtings {

     /**
      * Check that the Strings are anagram using Temporary storage array.
      * @param str1
      * @param str2
      * @return true/false.
      */
     private static boolean isAngrams(String str1, String str2) {
           int len = 0;
           if((len = str1.length())!= str2.length()) {
                return false;
           }
          
           int[] counts = new int[256];
           for (int i = 0; i < len; i++) {
                int ch1 = str1.charAt(i);
                int ch2 = str2.charAt(i);
               
                /**For first string increment count of character in count array. */
                counts[ch1] = counts[ch1] + 1;
                /**For second string decrement the count of character from count array. */
                counts[ch2] = counts[ch2] - 1;
           }

           /** Check if array contains only zero then strings are anagram otherwise not.*/
           for (int i = 0; i < len; i++) {
                if(counts[i]!=0) {
                     return false;
                }
           }
           return true;
     }
    
     /**
      * Driver method.
      * @param args
      */
     public static void main(String[] args) {
           String str1 = "geeksforgeeks";
           String str2 = "geeksfoeekrgs";
          
           boolean result = isAngrams(str1,str2);
           String angram = "Not Angram";
           if(result) {
                angram = "Angram";
           }
           System.out.println("Strings are "+angram);
     }
}

Time Complexity: O(n) and extra space required for temporary array.


No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...