-
Notifications
You must be signed in to change notification settings - Fork 0
/
group_anagrams.py
35 lines (29 loc) · 949 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
# Andy Yu
'''
Given an array of strings, group anagrams together.
For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:
[
["ate", "eat","tea"],
["nat","tan"],
["bat"]
]
Note:
For the return value, each inner list's elements must follow the lexicographic order.
All inputs will be in lower-case.
Difficulty: Medium
Solution notes:
Clever fast and short solution using Python tricks
d = collections.defaultdict(list)
for s in strs:
d[tuple(sorted(s))].append(s)
return [a for agram_group in d.values() if len(agram_group)>1 for a in agram_group]
O(n) time
O(n) space
'''
def group_anagrams(strs):
d = {}
for s in sorted(strs): # first sort to ensure inner list lexicographic order
key = "".join(sorted(s)) # this is the un-anagrammed key for each word, 'bac' gives key 'abc'
d[key] = d.get(key, []) + [s] # map -> key: 'abc', value: ['bac', 'cab', 'acb', etc.]
return [wl for wl in d.values()]