Microsoft Interview Question
Software Engineer in TestsAnother approach with O(n) space and time is use a hash to keep track of count of each char in string1, While parsing string2, decrement the count of the char in hash table(delete when count becomes zero). If hash table is empty at end, its anagram.
I will use extra space to solve this question, as sorting is a costly affair.
Regarding extra space, we only need to use memory for 256 character, not of O(n) if we know that string is made up of only ASCII characters. We can do more optimization on space, if we can put more restriction on our data type like if string will consist only of lower and upper character than I need space for only 50 characters......
From "http://www.careercup.com/question?id=18382"
solution was provided by "nirmalr" (modified slightly)
O(n) algorithm to check anagram :
+++++++++++++++++++++++++++++++++
variant of counting sort can be used here as the range is known.
algorithm :
input : string1, string2 (to be checked)
step 1: allocate one integer array c[26]
step 2: initialize elements of array c to zero
step 3 : for each character in string1
increment corresponding element in c by one (ex : for 'a', c[0]++)
step 4 : for each character in string2
decrement corresponding element in c by one (ex : for 'a', c[0]--)
step 5 : if "c" contains all zero then string1 & 2 are anagrams.
for optimization, step 3 and 4 can be merged together as they are independent activities.
i have a different approach using prime numbers.
all u need to do is maintain an array of first 26 prime numbers.
then for input string1 find its unique product value:
product_string1=1
for(i=0 to strlen(string1)) product_string1*=a[string[i]-'a']
if(strlen(string2)==strlen(string2)){
then find the product for string 2 in similar fashion
product_string2=1
for(i=0 to strlen(string2)) product_string2*=a[string[2]-'a']
if(product_string1==product_string2) string is anagram of string 1
}
Time complexity: Find the first 26 prime numbers, this will be done once only.
After that for every input it can said in o(n) time whether it is anagram or not where n is the string size. and space complexity is only int array of 26 to store first 26 prime numbers.
This question can also be inverted with a very clever trick: ensure two strings are not anagrams. In this case take XOR of two strings and see if it is non-zero :). I should ask this in the interview !
/**
* This follows a mathematical formula ab = cd & a+b=c+d cannot be the same for any numbers greater than 0
*/
public static void findAnagram(String str1, String str2)
{
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();
int sum = 0;
int mult = 0;
int sum2 = 0;
int mult2 = 0;
if(str1.length()!=str2.length()){System.out.println("An anagram should have the same length"); return;}
for(int i=0;i<str1.length();i++)
{
sum += str1.charAt(i);
mult *= str1.charAt(i);
sum2 += str2.charAt(i);
mult2 *= str2.charAt(i);
}
if(sum == sum2 && mult == mult2)
{
System.out.println("The strings are anagram");
}
}
I used a Hashmap, the complexity is O(n)
public class CheckAnagrams {
public static void main(String[] args){
String str1=new String();
String str2=new String();
Scanner s=new Scanner(System.in);
System.out.println("Enter the String1");
str1=s.nextLine();
System.out.println("Enter the String2");
str2=s.nextLine();
CheckAnagrams c=new CheckAnagrams();
System.out.println("the strings are anagrams: " + c.checkAnagrams(str1,str2));
}
boolean checkAnagrams(String str1, String str2){
HashMap<Character,Integer> h=new HashMap<Character, Integer>();
if(str1.length()!=str2.length()){
return false;
}
else
{ int dup ;
for(int i=0;i<str1.length();i++) {
dup=1;
if(h.containsKey(str1.charAt(i))) {
dup=h.get(str1.charAt(i));
dup++;
}
h.put(str1.charAt(i),dup);
}
for(int i=0;i<str2.length();i++) {
if(!h.containsKey(str2.charAt(i))) {
return false;
}
else{
dup=h.get(str1.charAt(i));
dup--;
h.put(str1.charAt(i),dup);
}
}
for(Character ch:h.keySet() ){
if(h.get(ch)>0){
return false;
}
}
return true;
}
}
}
sort the 2 words and compare if both strings are same then both are anagrams
- Anonymous November 14, 2009