## 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.

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

b'
\n\n

## Solution

\n
\n

#### Approach #1 (Sorting) [Accepted]

\n

Algorithm

\n

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.

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

Complexity analysis

\n
\n
• \n

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

\n
• \n
• \n

Space complexity : .\nSpace 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:

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

#### Approach #2 (Hash Table) [Accepted]

\n

Algorithm

\n

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.

\n

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.

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

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.

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

Complexity analysis

\n
\n
• \n

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

\n
• \n
• \n

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

\n
• \n
\n

\n

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

\n