Check whether two strings are anagram
  • Posted: 5 years ago
  • Edit
  • answers (1)
  • views (3121)

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


Posted Answers

Two strings are anagram of each other when they have same set of characters, but in different order. Let us assume that the input strings have the character set ASCII. The algorithm works as :


  • Compare the length of the two strings. Return false if they are not same.
  • Take an empty integer array of size \( 256 \) to hold the frequency of occurrence of characters in the string.
  • Iterate through the first string and increment the frequency of each character in its corresponding location in the integer array.
  • In the same time, iterate through the second string and decrement the frequency of the character in its corresponding location in the integer array.
  • Iterate through the integer array to check whether it has the value \( 0 \). If not, return false. Otherwise, return true.

Time complexity = \( O(n) \).



public static boolean checkTwoStringsAnagram(String string1, String string2){

/* Either string is null */
if (string1 == null || string2 == null)
return false;

/* Length of two strings are not same - return false */
if(string1.length() != string2.length())
return false;

/* Create an integer array to store the frequency of characters */
int[] charFrequency = new int[256];

/* Iterate through the strings */
for (int i = 0; i < string1.length(); i++){
/* increment frequency count in the first string */
charFrequency[string1.charAt(i)]++;
/* decrement frequency count in the second string */
charFrequency[string2.charAt(i)]--;
}

/* Check the frequency array */
for (int i = 0; i < 256; i++){
if (charFrequency[i] != 0)
/* Character set not same - Not an anagram */
return false;
}
/* Strings are anagram */
return true;
}



You need to Sign In to post your solution.