-
Notifications
You must be signed in to change notification settings - Fork 1
/
valid-anagram.py
36 lines (31 loc) · 1.14 KB
/
valid-anagram.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# https://leetcode.com/problems/valid-anagram/
# Related Topics: Hash Table, Sort
# Difficulty: Easy
# Initial thoughts:
# For a word to be an anagram of another word, it must have the exact
# same characters with the same quanitity as the other word, just in a
# different ordering.
# Using a hash map, we can create a frequency table from the first word
# and remove them from the frequency table while we go through the second
# word.
# If at the end the frequency table is empty, we have an anagram
# Time complexity: O(n) where n == len(s)
# Space complexity: O(1) because the freq tables won't have more than 26 chars
# (even if we were dealing with the whole unicode spectrum, it would be of constant
# complexity)
from typing import List
from collections import defaultdict
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
dic = defaultdict(int)
for c in s:
dic[c] += 1
for c in t:
if c in dic:
if dic[c] == 1:
del dic[c]
else:
dic[c] -= 1
else:
return False
return len(dic) == 0