Leetcode 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?

做法1：

把两个string都sort好，然后比较之。
Time: O(nlogn)
Space: O(1)

这样的话答案78.41%

public class Solution {
    public boolean isAnagram(String s, String t) {
        char[] ss = s.toCharArray();
        Arrays.sort(ss);
        String sss = new String(ss);
        char[] tt = t.toCharArray();
        Arrays.sort(tt);
        String ttt = new String(tt);
        return sss.equals(ttt);
    }
}

做法2： 用一个数组存起来
似乎比sort还要慢一些, 46.32%, 8ms。

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

Improve the 2nd solution: use a hashtable

import java.util.*;
public class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()) return false;
        
        Hashtable 
            theTableS = new Hashtable(),
            theTableT = new Hashtable();
        for (char i:s.toCharArray()) {
            if (theTableS.containsKey(i))
                theTableS.put(i,theTableS.get(i)+1);
            else theTableS.put(i,1);
        }
        for (char i:t.toCharArray()) {
            if (theTableT.containsKey(i)) 
                theTableT.put(i,theTableT.get(i)+1);
            else theTableT.put(i,1);
        }
        return theTableT.equals(theTableS);
    }
}