242. Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

Solution:

If two strings are anagram, the frequency of unique characters in string a should be exactly the same with string b.

Therefore, we use a HashMap to count the frequency of each character in string a first.

Then we check string b. When we meet a character, we decrease its frequency by 1 in the HashMap.

If we find the frequency of a character in the HashMap is less than 0, we know the number of this character in string b is more that that in string a. So they are not anagram.

The time complexity is O(n). We can treat the space complexity as O(1).



Code:

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] check = new int[256];
        for (char c : s.toCharArray()) {
            check[c]++;
        }
        for (char c : t.toCharArray()) {
            check[c]--;
            if (check[c] < 0) {
                return false;
            }
        }
        return true;
    }
}