[LeetCode/Python] 242. Valid Anagram

📌 Problem

[LeetCode] 242. Valid Anagram

📌 Solution

Solution 1: Use Counter

Code

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

Solution 2: Use dictionary

Code 2-1 (Before Refactoring)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        letters = {}
        for ls in s:
            if ls in letters:
                letters[ls] += 1
            else:
                letters[ls] = 1
        
        for lt in t:
            if lt in letters:
                if letters[lt] <= 0:
                    return False
                else:
                    letters[lt] -= 1
            else:
                return False
        return True

Code 2-2 (After Refactoring)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        letters = {}
        for c in s:
            letters[c] = letters.get(c, 0) + 1
        
        for c in t:
            if c not in letters or letters[c] == 0:
                return False
            letters[c] -= 1

        return True

Complexity

• Time: $O(n)$ ($n = |s| = |t|$)
• Space: $O(k)$ ($k$ = Number of unique characters, up to 26 for the alphabet or the entire Unicode set)

Follow-up

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

• In Python, dict and Counter already work with Unicode characters, so no code change is needed

• The only issue is case and normalization
  For example, "é" vs "e\u0301" look the same but are different code points. In such cases, use unicodedata.normalize() to unify them before comparison.