-
Notifications
You must be signed in to change notification settings - Fork 228
/
group-anagrams.py
43 lines (37 loc) · 887 Bytes
/
group-anagrams.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
37
38
39
40
41
42
43
# GROUP ANAGRAMS
def groupAnagrams(words):
# Write your code here.
anagrams = []
anagramCounts = []
for word in words:
letterCount = returnCount(word)
found = False
for i, count in enumerate(anagramCounts):
if count == letterCount:
found = True
anagrams[i].append(word)
break
if not found:
anagramCounts.append(letterCount)
anagrams.append([word])
return anagrams
# O(N) time and space
def returnCount(word):
count = {}
for letter in word:
if letter in count:
count[letter] += 1
else:
count[letter] = 1
return count
# O(Nlog(N) * w) time and O(w * N) space
def groupAnagrams(words):
# Write your code here.
anagrams = {}
for word in words:
sortedWord = "".join(sorted(word))
if sortedWord in anagrams:
anagrams[sortedWord].append(word)
else:
anagrams[sortedWord] = [word]
return list(anagrams.values())