Question

LeetCode Link | 242. Valid Anagram | Easy

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Constrains

  • 1 <= s.length, t.length <= 5 * 10^4
  • s and t consist of lowercase English letters.

Examples

Example 1

Input: s = “anagram”, t = “nagaram”
Output: true

Example 2

Input: s = “rat”, t = “car”
Output: false

Solution Approach

Method: Array / Hash Table

Constrains

  • None

This method does not have any limitations.

Concept Explanation

We can use a hash table to solve the problem, and in fact, an array is a simple hash table.

In this problem, since the string only contains lowercase characters, we can define an array to record the frequency of each character in string s.

How large should this array be? Define an array called record, size 26 will suffice, initialized to 0, because there are 26 continuous ASCII values from character ‘a’ to ‘z’.

When traversing the string s, you simply need to increment the element at the index s[i] - 'a' by 1. There’s no need to remember the ASCII value of ‘a’; a relative value is sufficient. This way, the occurrences of each character in string s are counted.

Next, let’s see how to check whether these characters appear in string t. Similarly, while traversing string t, decrement the value at the hashed index corresponding to each character in t.

Simple Hash Table

At the end, check the record array: if any element is not zero, it indicates that either string s or t has extra or missing characters, hence return false.

If all elements of the record array are zero, it means that strings s and t are anagrams of each other, so return true.

Code

  • Time complexity: O(n)
  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
10
function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false;
    let helperArr: number[] = new Array(26).fill(0);
    let pivot: number = 'a'.charCodeAt(0);
    for (let i = 0; i < s.length; i++) {
        helperArr[s.charCodeAt(i) - pivot]++;
        helperArr[t.charCodeAt(i) - pivot]--;
    }
    return helperArr.every(i => i === 0);
};

Conclusion

This is great question to start practicing knowledge of the Hash Table, it simply mapping the each character into a 26 length array which let you know the concept of the Hash Table.