Problem
Given two strings s and t, return true if t is an anagram of s (uses the exact same characters in any order).
Example
Input: s = "anagram", t = "nagaram"
Output: trueInput: s = "rat", t = "car"
Output: falseSolution
Count the frequency of each character. Anagrams have identical character counts.
def is_anagram(s, t):
if len(s) != len(t):
return False
counts = {}
for ch in s:
counts[ch] = counts.get(ch, 0) + 1
for ch in t:
if counts.get(ch, 0) == 0:
return False
counts[ch] -= 1
return Truefunction isAnagram(s, t) {
if (s.length !== t.length) return false;
const counts = {};
for (const ch of s) counts[ch] = (counts[ch] || 0) + 1;
for (const ch of t) {
if (!counts[ch]) return false;
counts[ch]--;
}
return true;
}bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
int counts[26] = {0};
for (char ch : s) counts[ch - 'a']++;
for (char ch : t) {
if (--counts[ch - 'a'] < 0) return false;
}
return true;
}public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] counts = new int[26];
for (char ch : s.toCharArray()) counts[ch - 'a']++;
for (char ch : t.toCharArray()) {
if (--counts[ch - 'a'] < 0) return false;
}
return true;
}Complexity
- Time: O(n)
- Space: O(1) for fixed alphabet
Explanation
For lowercase English letters, a fixed-size array of 26 is faster than a hash map. Increment for one string, decrement for the other. If anything goes negative, they’re not anagrams.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?