-
Notifications
You must be signed in to change notification settings - Fork 29
/
Copy path0049-Group-Anagrams.py
85 lines (64 loc) · 1.94 KB
/
0049-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
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
83
84
85
'''
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
Constraints:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] consists of lower-case English letters.
'''
from typing import List
# Using Hash Table without sorting
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = {}
for s in strs:
key = [0] * 26
for c in s:
key[ord(c) - ord('a')] += 1
key = tuple(key)
if key in d:
d[key].append(s)
else:
d[key] = [s]
return d.values()
# Using Sorting and Hash Table
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d= {}
for s in strs:
key = sorted(s)
key = ''.join(key)
if key in d:
d[key].append(s)
else:
d[key] = [s]
result = []
for key, value in d.items():
result.append(value)
return result
# Using function to find Hash in Hash Table
class Solution:
def findHash(self, s):
return ''.join(sorted(s))
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = {}
for s in strs:
key = self.findHash(s)
if key in d:
d[key].append(s)
else:
d[key] = [s]
return d.values()
# Custom Input Check
s = Solution()
answer = s.findHash(["tan","ant","act","cat"]) # [["tan","ant"],["act","cat"]]
print(answer)