Part 2 · Problems · Arrays and hashing
Valid Anagram
#242 · Easy · LeetCode
Return true if t is a rearrangement of the letters of s.
s = anagram, t = nagaram -> true s = rat, t = car -> false
Ask before coding
- Only lowercase a to z, or any Unicode?
- Is case significant?
Hint
Same letters, same counts.
Approach
If lengths differ, false. Count letters of s in a Map, then subtract for t. If any count goes below zero, false.
Time O(n) Space O(k), k = distinct characters
Watch it run
Solution (JavaScript, tested)
function isAnagram(s, t) {
if (s.length !== t.length) return false;
const count = new Map();
for (const c of s) count.set(c, (count.get(c) ?? 0) + 1);
for (const c of t) {
const left = (count.get(c) ?? 0) - 1;
if (left < 0) return false;
count.set(c, left);
}
return true;
}Traps
- Forgetting the length check.
- For only a to z, a fixed array of 26 is faster than a Map.
Say out loud: Anagrams have identical character counts. I'll count one string up and the other down.