Valid Anagram

Problem

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.

Solution

Array as HashTabel Solution: O(n) time and O(1) space

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] letters = new int[26];
        for (int i = 0; i < s.length(); i++) {
            letters[s.charAt(i) - 'a']++;
            letters[t.charAt(i) - 'a']--;
        }
        for (int count : letters) {
            if (count != 0) return false;
        }
        return true;
    }
}

Concise Sorting Solution: O(nlgn) time and O(1) space

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] c1 = s.toCharArray(), c2 = t.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        return Arrays.equals(c1, c2);
    }
}

Analysis

The first solution use HashMap to count the frequency of all letters from two strings
As long as two strings are anagram, the frequency of each letter ought to be 0
While the second solution approaches from a different direction
We get the char[] from each string and then sort them
Then they should be equal if two strings are anagram