This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #242 (Easy): Valid Anagram
Description:
Given two strings s and t, write a function to determine if t is an anagram of s.
Examples:
| Example 1: | |
|---|---|
| Input: | s = "anagram", t = "nagaram" |
| Output: | true |
| Example 2: | |
|---|---|
| Input: | s = "rat", t = "car" |
| Output: | false |
Constraints:
- You may assume the string contains only lowercase alphabets.
Idea:
An anagram of a word is basically another word that uses the same letters with the same frequency, just in a different order. Since we only care about the letters and their frequency, the easy choice is to use a frequency map.
Since we're dealing with lowercase letters, we can make this more performant by using an Array instead of a more traditional Map, and converting the characters to their unicode number (97 - 122) for storage.
First, we iterate through the first string S and increment each character code position in our frequency map (fmap). Then we run through the second string T and decrement the character code positions in fmap. If we ever go below 0 then we know we've got a character frequency in T that isn't the same as S, so we should return false.
If we get to the end with no problem, though, we should return true.
Implementation:
In javascript, we can use a typed array Int16Array to make the process even more performant.
Python has a string function count() that makes this problem even faster.
Javascript Code:
var isAnagram = function(S, T) {
let len = S.length, fMap = new Int16Array(123)
if (T.length !== len) return false
for (let i = 0; i < len; i++)
fMap[S.charCodeAt(i)]++
for (let i = 0; i < len; i++)
if (--fMap[T.charCodeAt(i)] < 0) return false
return true
};
Python Code:
class Solution:
def isAnagram(self, S: str, T: str) -> bool:
SMap = {c: S.count(c) for c in set(S)}
TMap = {c: T.count(c) for c in set(T)}
return SMap == TMap
Java Code:
class Solution {
public boolean isAnagram(String S, String T) {
int len = S.length();
int[] fMap = new int[123];
if (T.length() != len) return false;
for (int i = 0; i < len; i++)
fMap[S.codePointAt(i)]++;
for (int i = 0; i < len; i++)
if (--fMap[T.codePointAt(i)] < 0) return false;
return true;
}
}
C++ Code:
class Solution {
public:
bool isAnagram(string S, string T) {
int len = S.length();
int fMap [123] = {0};
if (T.length() != len) return false;
for (int i = 0; i < len; i++)
fMap[int(S[i])]++;
for (int i = 0; i < len; i++)
if (fMap[int(T[i])]-- == 0) return false;
return true;
}
};
Top comments (1)
Since lower case letters are only 26 in number, we can use an array of size 26 instead and for getting the right index, we can subtract 97 from the ASCII code. So 'a''s index would become 97-97 = 0. Might not be significant but still an optimization.