Understanding Valid Anagrams
An anagram is a word or phrase formed by rearranging the letters of another. The Valid Anagram problem asks us to determine if two strings are anagrams of each other.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
1. Sorting Approach
The simplest solution is to sort both strings and compare them.
def isAnagram_sorting(s: str, t: str) -> bool:
if len(s) != len(t):
return False
return sorted(s) == sorted(t)
Time: O(n log n)
Space: O(1)
2. Hash Map Approach
Using a hash map to count character frequencies in both strings.
| Character |
a |
n |
g |
r |
m |
| Frequency |
3 |
1 |
1 |
1 |
1 |
from collections import Counter
def isAnagram_hashmap(s: str, t: str) -> bool:
if len(s) != len(t):
return False
return Counter(s) == Counter(t)
Time: O(n)
Space: O(k)
3. Array Approach (Optimal)
Using a fixed-size array to count character frequencies.
| Index |
0 (a) |
6 (g) |
12 (m) |
13 (n) |
17 (r) |
| Count |
0 |
0 |
0 |
0 |
0 |
def isAnagram_array(s: str, t: str) -> bool:
if len(s) != len(t):
return False
count = [0] * 26
for i in range(len(s)):
count[ord(s[i]) - ord('a')] += 1
count[ord(t[i]) - ord('a')] -= 1
return all(x == 0 for x in count)
Time: O(n)
Space: O(1)
Common Edge Cases
# Empty strings
s = "", t = ""
# Different lengths
s = "rat", t = "rats"
# Same letters, different counts
s = "aaab", t = "aaba"
# Case sensitivity
s = "Anagram", t = "nagaram"
# Special characters
s = "rat!", t = "tar!"
Implementation Tips
- Always check if the strings have the same length first
- Consider whether the solution needs to be case-sensitive
- Think about how to handle special characters
- Choose the approach based on the constraints and requirements
Launch your Graphy