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())

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)

Blog

leetcode 49. Group Anagrams (python)

smolthing

Solution 1

Solution 2

Join Our Newsletter. No Spam, Only the good stuff.

Related