Solution


Approach #1 (Sorting) [Accepted]

Algorithm

An anagram is produced by rearranging the letters of into . Therefore, if is an anagram of , sorting both strings will result in two identical strings. Furthermore, if and have different lengths, must not be an anagram of and we can return early.

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

Complexity analysis

  • Time complexity : . Assume that is the length of , sorting costs and comparing two strings costs . Sorting time dominates and the overall time complexity is .

  • Space complexity : . Space depends on the sorting implementation which, usually, costs auxiliary space if heapsort is used. Note that in Java, toCharArray() makes a copy of the string so it costs extra space, but we ignore this for complexity analysis because:

    • It is a language dependent detail.
    • It depends on how the function is designed. For example, the function parameter types can be changed to char[].

Approach #2 (Hash Table) [Accepted]

Algorithm

To examine if is a rearrangement of , we can count occurrences of each letter in the two strings and compare them. Since both and contain only letters from , a simple counter table of size 26 is suffice.

Do we need two counter tables for comparison? Actually no, because we could increment the counter for each letter in and decrement the counter for each letter in , then check if the counter reaches back to zero.

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

Or we could first increment the counter for , then decrement the counter for . If at any point the counter drops below zero, we know that contains an extra letter not in and return false immediately.

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

Complexity analysis

  • Time complexity : . Time complexity is because accessing the counter table is a constant time operation.

  • Space complexity : . Although we do use extra space, the space complexity is because the table's size stays constant no matter how large is.

Follow up

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

Answer

Use a hash table instead of a fixed size counter. Imagine allocating a large size array to fit the entire range of unicode characters, which could go up to more than 1 million. A hash table is a more generic solution and could adapt to any range of characters.