Oracle Interview Question
Software Engineer / Developers// Write a method to decide if two strings are anagrams or not.
// Complexity O ( 2n + k) avg, since s1 and s2 should contains the same length otherwise It will return false immediate
public static boolean isAnagram(char s1[], char s2[]){
if(s1.length != s2.length) return false;
int letters [] = new int[256];
for( int i = 0; i < s1.length; i++){
letters[toUpperCase(s1[i])]++;
}
for( int j = 0; j < s2.length; j++){
letters[toUpperCase(s2[j])]--;
if(letters[toUpperCase(s2[j])] < 0) return false;
}
for(int x = 0; x < letters.length; x++){
if(letters[x] != 0 ) return false;
}
return true;
}
What if you character set is not ASCII (256) but UNICODE (2^16 or something)? The complexity of the above solution would be enormous.
public static boolean isAnagram(String word, String anagram) {
if(word.length() != anagram.length())
return false;
char[] chars = word.toCharArray();
for(char c : chars)
{
int index = anagram.indexOf(c);
if(index != -1){
anagram = anagram.substring(0,index) +
anagram.substring(index +1, anagram.length());
}
else {
return false;
}
}
return anagram.isEmpty();
}
Time Complexity: O(n)
public static boolean IsAnagram(String str1, String str2){
if(str1.length() != str2.length()){
return false;
}
char[] charArr1 = str1.toLowerCase().toCharArray();
char[] charArr2 = str2.toLowerCase().toCharArray();
Character c;
int hashCodeValue1 =0;
int hashCodeValue2 =0;
for(int i=0;i<charArr1.length;i++){
c = charArr1[i];
hashCodeValue1+=c.hashCode();
}
for(int i=0;i<charArr2.length;i++){
c = charArr2[i];
hashCodeValue2+=c.hashCode();
}
if(hashCodeValue1 == hashCodeValue2)
return true;
return false;
}
i think xoring of all integers values of characters should be 0 if they are anagram.
- amit January 30, 2014