smolthing
https://leetcode.com/problems/group-anagrams
Solution 1
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
sortedKeyDict = defaultdict(list)
for i in strs:
sortedKey = sorted(i)
sortedKeyInString = ''.join(sortedKey)
sortedKeyDict[sortedKeyInString].append(i)
return list(sortedKeyDict.values())
- Use sorted word as dictionary key
Time Complexity: O(nklog(k))
Space Complexity: O(nk)
Solution 2
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
sortedKeyDict = defaultdict(list)
for i in strs:
characterFrequency = [0]*26
for j in i:
index = ord(j) - ord('a')
characterFrequency[index] += 1
sortedKeyDict[tuple(characterFrequency)].append(i)
return list(sortedKeyDict.values())
- Use character frequency count as dictionary key
- Convert list to tuple to make it hashable as dictionary key
Time Complexity: O(nk)
Space Complexity: O(nk)
