This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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?

b'

\n\n## Solution

\n

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

\n\n

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

\n\n\n

'
\n

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

\npublic 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

**Complexity analysis**

- \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

\n`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
- 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

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

\nDo 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) {\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

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.

\npublic 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

**Complexity analysis**

- \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

**Follow up**

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

\n**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.

\n