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;
}
};
Discussion (0)