You are given two strings s and t of lowercase English letters.
Return true if t is an anagram of s: it uses exactly the same letters, each exactly as many
times, possibly in a different order. Otherwise return false.
Example 1
- Input
- s = "listen", t = "silent"
- Output
- true
e, i, l, n, s and t once each.Example 2
- Input
- s = "aab", t = "abb"
- Output
- false
a and b, but s has two as and t has one.Constraints
sandteach hold 1 to 5 × 10⁴ letters.- Both contain only the lowercase letters
atoz.
Show the pattern
Hashing
Two words are anagrams exactly when every letter appears equally often in both. Counting letters is a job for a hash map (or a table of 26 counts).
See hashing in a visualiserShow the approach
If the lengths differ, return false. Otherwise count each letter of s in a hash map (or an
array of 26 counts), then walk through t, taking one off the count of each of its letters. If a
count is already 0 when you need to take one off, t uses that letter more often than s does:
return false. If you get to the end, every count matched, so the strings are anagrams.
Sorting both strings and comparing them also works, in O(n log n).
Time: O(n) · Space: O(1): at most 26 counts