242. Valid Anagram¶

Difficulty: easy
LeetCode: https://leetcode.com/problems/valid-anagram/
Topics: Hash Table, String, Sorting

Solutions¶

Language	Approach	Time	Space	File
python	Map	`O(n + m)`	`O(n)`	`python/map_solution.py`

Map — python¶

Time: O(n + m)
Space: O(n)

python/map_solution.py

# Time: O(n + m)
# Space: O(n)

from collections import Counter

from task import Task


class MapSolution(Task):
    def isAnagram(self, s: str, t: str) -> bool:
        counts = Counter(s)
        for ch in t:
            if ch in counts:
                counts[ch] -= 1
                if counts[ch] == 0:
                    counts.pop(ch)
            else:
                return False
        return len(counts) == 0

Traces¶

Map¶

Map trace¶

Step 1¶

s: anagram
t: nagaram
 ^
m: a=3 n=1 g=1 r=1 m=1

Step 2¶

s: anagram
t: nagaram
   ^
m: a=3 n=0 g=1 r=1 m=1

Step 3¶

s: anagram
t: nagaram
    ^
m: a=2 g=1 r=1 m=1

Step 4¶

s: anagram
t: nagaram
     ^
m: a=2 g=0 r=1 m=1

Step 5¶

s: anagram
t: nagaram
      ^
m: a=1 r=1 m=1

Step 6¶

s: anagram
t: nagaram
       ^
m: a=1 r=0 m=1

Step 7¶

s: anagram
t: nagaram
        ^
m: a=0 m=1

Step 8¶

s: anagram
t: nagaram
         ^
m: m=0

Step 9¶

s: anagram
t: nagaram
          ^
m: []
output: true