Sunday, March 1, 2015

Check anagrams


check if two strings are anagrams 

My first thought is always hash map, however, since hash map itself is array implementation, it will never be faster than actually using an array. So this time I am going to use an array. Create a char array with length of 256 (extended ascii table). Create another variable, uniqChar, for unique characters in the string. Go through the first string, track number of unique characters and occurrence of each character in the string.
Go through the second array, if any character doesn't exist in the first string all the occurrence in the second string is more than that in the first string(letter[i] == 0), return false. For any letter in string s1, if the occurrence in s2 equals that in s1, we assume this letter has been checked in s2, thus we decrement uniqChar. If uniqChar == 0, the only situation where we should return true is that s2 reaches to the end.


public static boolean areAnagrams2(String s1, String s2){
     if (s1 == null || s2 == null || s1.length() != s2.length())
         return false;
     char[] letters = new char[256];
     int uniqChar = 0;
     for (int i = 0; i < s1.length(); i++){
         int ch = (int)s1.charAt(i);
         if(letters[ch] == 0)
             uniqChar++;
         letters[ch]++;
     }
     for (int i = 0; i < s2.length(); i++){
         int ch = (int)s2.charAt(i);
         if (letters[ch] == 0)
             return false;
         letters[ch]--;
         if (letters[ch] == 0)
             uniqChar--;
         if (uniqChar == 0)
             return i == s2.length() - 1;
     }
     return uniqChar == 0;
 }

No comments:

Post a Comment