49. Group Anagrams
## description
## 49. Group Anagrams
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation:
- –There is no string in strs that can be rearranged to form "bat".
- –The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
- –The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
- –1 <= strs.length <= 104
- –0 <= strs[i].length <= 100
- –strs[i] consists of lowercase English letters.
Constraints:
## notes
### Intuition
Anagrams have identical character frequencies. By using the frequency distribution as a key, all anagrams will hash to the same bucket.
### Implementation
Use a hashmap where keys represent frequency distributions and values are lists of anagrams. For each string, build a 26-element frequency array. Use this as the key to group strings together. Finally, collect all the values from the map as the result.
### Edge-cases
Python doesn't allow lists as dictionary keys. Convert the frequency array to a tuple or comma-separated string to make it hashable.
- –Time: O(n * k) — where n is the number of strings and k is the maximum string length
- –Space: O(n * k) — storing all strings in the hashmap
### Complexity
## solution
1from typing import List
2class Solution:
3 def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
4 map = {}
5 for s in strs:
6 freq = [0] * 26
7 for c in s:
8 freq[ord(c) - ord('a')] += 1
9
10 freq_str = ",".join([str(f) for f in freq])
11 if freq_str in map:
12 map[freq_str].append(s)
13 else:
14 map[freq_str] = [s]
15
16 ans = []
17 for key in map:
18 ans.append(map[key])
19
20 return ans
21
22
23
24
25if __name__ == "__main__":
26 # Include one-off tests here or debugging logic that can be run by running this file
27 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
28 solution = Solution()
29 print(solution.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
30