LeetCode 242 - Valid Anagram

2026-04-01

easy　array

Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Example 1:

Input: s = "racecar", t = "carrace"

Output: true

Example 2:

Input: s = "jar", t = "jam"

Output: false

Solution:

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # hash map solution
        # Time Complexity: O(N). Since we have an early exit if len(s) != len(t), N is guaranteed to equal M. 
        # We iterate through both strings to build the frequency maps, which takes O(N) time. 
        # It may also trigger an early exit during the second loop if a character in 't' is not found in the 's' map.
        # Space Complexity: O(1). Although we create two hash maps, the space is strictly bounded 
        # to at most 26 lowercase English letters, making it constant space.
        if len(s) != len(t):
            return False
        s_count_map = {}
        for i in s:
            if i not in s_count_map:
                s_count_map[i] = 1
            else:
                s_count_map[i] += 1

        t_count_map = {}
        for i in t:
            if i not in s_count_map:
                return False

            if i not in t_count_map:
                t_count_map[i] = 1
            else:
                t_count_map[i] += 1
        for k, v in t_count_map.items():
            if t_count_map[k] != s_count_map[k]:
                return False
        return True