DEV Community

smolthing
smolthing

Posted on

leetcode 49. Group Anagrams (python)

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())
Enter fullscreen mode Exit fullscreen mode
  1. 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())
Enter fullscreen mode Exit fullscreen mode
  1. Use character frequency count as dictionary key
  2. Convert list to tuple to make it hashable as dictionary key

Time Complexity: O(nk)
Space Complexity: O(nk)

Top comments (0)