Group Anagrams
MediumBucket words by their sorted signature
Words made of the same letters get the same sorted key, so drop them into the same bucket.
The idea
Anagrams share the same sorted letters (or the same letter-count signature). Use that signature as a map key and drop each word into its bucket.
eat
tea
tan
ate
nat
0
1
2
3
4
Step 1 of 7. Anagrams share the same sorted signature — bucket words by that key. Values: eat, tea, tan, ate, nat.
1/7
Optimal
timeO(n·k)spaceO(n·k)
Key = letter counts.
1const groups = new Map();2for (const w of words) {3 const key = countSignature(w); // e.g. "1a1e1t"4 (groups.get(key) ?? groups.set(key, []).get(key)).push(w);5}6return [...groups.values()];Input
- array
- [eat, tea, tan, ate, nat]
Memory
- key
- —
Output
- groups
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- strs = ["eat","tea","tan","ate","nat","bat"]
- Output:
- [['ate', 'eat', 'tea'], ['nat', 'tan'], ['bat']]
- Explanation:
- Words with the same letters land together.
Example 2
- Input:
- strs = [""]
- Output:
- [['']]
- Explanation:
- A single empty string is its own group.
Example 3
- Input:
- strs = ["a"]
- Output:
- [['a']]
- Explanation:
- One word, one group.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.