Group Anagrams into subsets: Python
Mon Sep 19 2022 22:07:04 GMT+0000 (UTC)
Saved by
@bryantirawan
#python
#neetcode
#sort
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
def Remove(lst): #to remove repeats at end
return ([list(i) for i in {*[tuple(sorted(i)) for i in lst]}])
result = []
for i in range(0, len(strs)):
anagram_subset = [strs[i]]
sorted_string = sorted(strs[i])
for d in range(0, len(strs)):
#to avoid repeat
#maybe change to start, end pointers to avoid making duplicate in first place?
if d == i:
continue
if sorted(strs[d]) == sorted_string:
anagram_subset.append(strs[d])
anagram_subset.sort()
result.append(anagram_subset)
anagram_subset = []
return Remove(result)
#Big O is n * n * n log N lol
#more efficient solution
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = defaultdict(list) #map charCount to list of anagrams
for s in strs:
count = [0] * 26 # a ... z
for c in s:
count[ord(c) - ord("a")] += 1 #mapping to ASCII and then adding 1 so that a = 1, b = 2, etc.
res[tupule(count)].append(s)
return res.values()
#big O(m * n * 26) which is just (m * n)
content_copyCOPY
When dealing with creating sublists, usually need to figure out a way to remove duplicates at end and during nested for loop.
https://leetcode.com/problems/group-anagrams/
Comments