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