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).
packagecrack.coding.interview;
importjava.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 voidmain(String[] args) {
String str1 = "geeksforgeeks";
String str2 = "geeksfoeekrgs";
booleanresult = 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.
packagecrack.coding.interview;
importjava.util.Arrays;
public class AngramSrtings {
/**
* Check that the Strings are anagram using Temporary storage array.
* @param str1
* @param str2
* @return true/false.
*/
private static booleanisAngrams(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 voidmain(String[] args) {
String str1 = "geeksforgeeks";
String str2 = "geeksfoeekrgs";
booleanresult = 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