> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/arrays ]
> [project group:: Neetcode 150]
> [difficulty:: medium]
> [status:: done]
> [link:: https://leetcode.com/problems/group-anagrams/]
> [up:: [[Leetcode MOC]]]
## Problem
Given an array of strings `strs`, group **the anagrams** together. You can return the answer in **any order**.
An **Anagram** is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
**Example 1:**
**Input:** strs = ["eat","tea","tan","ate","nat","bat"]
**Output:** [["bat"],["nat","tan"],["ate","eat","tea"]]
**Example 2:**
**Input:** strs = [""]
**Output:** [[""]]
**Example 3:**
**Input:** strs = ["a"]
**Output:** [["a"]]
**Constraints:**
- `1 <= strs.length <= 104`
- `0 <= strs[i].length <= 100`
- `strs[i]` consists of lowercase English letters.
## Solution
### Mine
#### Python
```python
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagram_cache = []
result = []
for word in strs:
sorted_word = sorted(word)
if sorted_word not in anagram_cache:
anagram_cache.append(sorted_word)
result.append([word])
else:
for idx, cached in enumerate(anagram_cache):
if cached == sorted_word:
result[idx].append(word)
break
return result
```
#### Rust
### Neetcode
```python
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord("a")] += 1 # This indexes the ASCII representation normalized to where "a" is 0.
res[tuple(count)].append(s)
return res.values()
```
## Things I Learned
With anagrams, sorting is the brute force way.
### Neetcode
Two words are anagrams if their sorted versions are equal. However, time complexity is $m \cdot n\:log\:n$, and we can do better than that.
Instead, for each string, get count of each character. So use a hash map, where the key is the pattern of the count (e.g. 1 e, 1 a, 1 t), and the value is the list of the words that are anagrams. This makes overall time complexity is $O(m \cdot n)$ where m is length of array and n is length of strings.
The pattern of the count is just a list (cast into a tuple) where each position is the count of that latter (ie position 0 represents the number of As).
## Scratchpad
Thought here is to do it in one-ish pass. For each input string, check against return array. To check anagram membership, each group should have a dict where the key is each letter and the value is the number of times that letter is in the word. The index should be the index of that group within the return array.
This seems brute forcey. And probably won't work becuase we can't really check the count of each letter in one pass.
---
DUH. Just need to sort the inputs to check if they're anagrams. At the expense of some memory complexity, we can also cache each sorted item in a list where the position marks the group in the return array.