Leetcode 242 - Valid Anagram

Difficulty: easy

Table of contents

Open Table of contents

Problem

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.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Constraints:

Follow-up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Explanation/Approach

To determine if two strings are anagrams, we must ensure that they have the same characters in the same quantities. This can be done in several ways:

Solution 1: Sorting

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # Sort both strings and compare them
        return sorted(s) == sorted(t)

Time and Memory Complexity

The time complexity is O(n log n) due to the sorting, where n is the length of the strings. The space complexity is O(1) if we assume the sorting is done in-place.

Explanation

This solution sorts both strings and then compares them. If they are equal, then one is an anagram of the other.

Solution 2: Hash Table Count

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # If the lengths differ, they cannot be anagrams
        if len(s) != len(t):
            return False

        # Count characters in both strings
        count = {}
        for char in s:
            count[char] = count.get(char, 0) + 1
        for char in t:
            count[char] = count.get(char, 0) - 1

        # Check if all counts are zero
        return all(value == 0 for value in count.values())

Time and Memory Complexity

The time complexity is O(n), where n is the length of the strings, since each character is visited once. The space complexity is O(1), as the hash table will have at most 26 key-value pairs (for the letters in the alphabet).

Explanation

This solution counts the occurrences of each character in s and t. It first increments the count for each character in s and then decrements it for each character in t. If the counts are all zero, the strings are anagrams of each other.

Follow-Up: Unicode Characters

For Unicode characters, the hash table approach still works. However, the key space can be much larger, depending on the range of Unicode characters used. The principle remains the same: count the occurrences of each character in both strings and compare the counts.

Certainly! Let’s add a visual representation to the explanations, especially focusing on the Hash Table Count approach, as it’s more illustrative for this problem.

Visual Representation for Solution 2: Hash Table Count

Consider the strings s = "anagram" and t = "nagaram" as an example.

  1. Building the Character Count for s:

    s = "anagram"
Count = {'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1}

  2. Updating the Count with Characters from t:

    t = "nagaram"
Update Count = {'a': 0, 'n': 0, 'g': 0, 'r': 0, 'm': 0}

    The count for each character is incremented while processing s and decremented while processing t.

  3. Checking the Final Counts:

    • All values in the Count are 0, indicating an equal number of each character in s and t.

  4. Return Result:

    • Since all counts are zero, the function returns True, confirming s and t are anagrams.

In this visual process, it’s clear that the counts of characters in both strings match exactly, demonstrating they are anagrams. This method efficiently manages the character frequencies and makes the comparison straightforward.