seanpgallivan

Posted on

# Solution: Valid Anagram

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;
}
};
``````