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