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.

Solution1: sort two strings first and then comparing them. Run time complexity is O(n), space complexity is O(n).
Arrays.sort(int[] a) in recent JDK is implemented with Dual-pivot Quicksort algorithm which has O(n log n) average complexity and is performed in-place.

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        } else if (s.length() == 0 && t.length() == 0) {
            return true;
        }
        
        char[] arrS = new char[s.length()];
        char[] arrT = new char[t.length()];
        for (int i = 0; i < s.length(); i++) {
            arrS[i] = s.charAt(i);
        }
        for (int i = 0; i < t.length(); i++) {
            arrT[i] = t.charAt(i);
        }
        
        Arrays.sort(arrS);
        Arrays.sort(arrT);
        
        for (int i = 0; i < arrS.length; i++) {
         if (arrS[i] != arrT[i]) {
             return false;
         }
        }
        return true;
    }
}

Or: 简洁一点的写法

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        } 
        
        char[] arrS = s.toCharArray();
        char[] arrT = t.toCharArray();
        
        Arrays.sort(arrS);
        Arrays.sort(arrT);
        
        for (int i = 0; i < arrS.length; i++) {
         if (arrS[i] != arrT[i]) {
             return false;
         }
        }
        return true;
    }
}

Solution2: HashMap. Run time complexity is O(n), space complexity is O(n).

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        } else if (s.length() == 0 && t.length() == 0) {
            return true;
        }
        
        HashMap map = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            char key = s.charAt(i);
            if (map.containsKey(key)) {
                map.put(key, map.get(key) + 1);
            } else {
                map.put(key, 1);
            }
        }
        
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
            } else {
                return false;
            }
        }
        
        Set keys = map.keySet();
        for (char k : keys) {
            if (map.get(k) != 0) {
                return false;
            }
        }
        
        return true;
    }
}