[LeetCode] 049. Group Anagrams

• Problem (Medium)
• Approach 1: (My Solution - Beat 100.00% Python) Create a Dictionary
  • Idea
  • Solution
  • Complexity

Problem (Medium)

049. Group Anagrams

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

All inputs will be in lowercase. The order of your output does not matter.

Approach 1: (My Solution - Beat 100.00% Python) Create a Dictionary

Idea

Create dictionary to save the anagrams’ characters (sorted) as the keys, and the strings in str that satisfying anagrams rule as the values.

Solution

class Solution1:
    def groupAnagrams(self, strs):
        """ 
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        pool = {}
        for s in strs:
            check = tuple(sorted([i for i in s]))
            if not pool.get(check):
                pool[check] = [s] 
            else:
                pool[check].append(s)
        return set([tuple(sorted(i)) for i in pool.values()])

Complexity

• Time: $O(NK\log K)$ where $N$ is the length of strs, and $K$ is the maximum length of a string in strs.
• Space: $O(NK)$

KF