LeetCode #49 Group Anagrams

Medium

Problem

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.

Solution — Counting Tuple

Use a tuple with 26 dimensions to save occurrence of every letter of each string. Then use this tuple as hash key to group anagrams.

Complexity

It scan each character of every string in strs, so it will take O(mn) time if m and n denote to the length of strs and the length of string with the maximum length in strs. For insertion of hash map, it may cost O(1)/O(logm) time in average/worst cases. Therefore, it’s time complexity will be O(mn)/O(mnlogm) in average/worst cases.

For space complexity, because there may exist mn difference hash key in hash map, it uses O(mn) extra space.

Solution — Prime Bases

Instead of using a tuple to save counts as hash key, we can manually map 26 letters to 26 different primes and multiply every mapping prime of a string as the hash key.

For example, if a = 2, b = 3, c = 5, abc will be 2 * 3 * 5 = 30 which is also the hash key of cab.

Complexity

It’s complexity is the same with counting tuple approach:

• time complexity is O(mn)/O(mnlogm) in average/worst cases
• space complexity is O(mn)

Follow up

One can try to write a function to get all primes instead of manually assigning them. This problem may be a good reference.