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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
"""
Question
Anagram Groups
Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.
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: strs = ["act","pots","tops","cat","stop","hat"]
Output: [["hat"],["act", "cat"],["stop", "pots", "tops"]]
Example 2:
Input: strs = ["x"]
Output: [["x"]]
Example 3:
Input: strs = [""]
Output: [[""]]
Constraints:
1 <= strs.length <= 1000.
0 <= strs[i].length <= 100
strs[i] is made up of lowercase English letters.
"""
from collections import defaultdict
from typing import Dict, List
class Solution:
def dictionary(self, strs: List[str]) -> List[List[str]]:
res: Dict = defaultdict(list)
for s in strs:
count: List[int] = [0] * 26
for c in s:
count[ord(c) - ord("a")] += 1
res[tuple(count)].append(s)
return list(res.values())
case1 = ["act", "pots", "tops", "cat", "stop", "hat"]
case2 = ["x"]
case3 = [""]
solution = Solution()
print(f" dictionary case1: {solution.dictionary(case1)}")
print(f" dictionary case2: {solution.dictionary(case2)}")
print(f" dictionary case3: {solution.dictionary(case3)}")
"""
Solution
url: https://neetcode.io/problems/anagram-groups
video: https://youtu.be/vzdNOK2oB2E
1. dictionary
time: O(m*n*26) = O(m*n)
space: O()
code:
```python
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
ans = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord("a")] += 1
ans[tuple(count)].append(s)
return ans.values()
```
"""
|
