Group Anagrams Extended
Medium · Arrays & Hashing · Array · Hash Table · String · Counting
Problem
You are given an array of strings strs that may contain upper- and lower-case letters, spaces and punctuation. Two strings belong to the same group when they are anagrams after normalization: lower-case every letter and discard every character that is not a letter.
Return the groups. Keep each original string exactly as given. Within a group, list the strings in the order they appear in strs, and order the groups by the position of their first member.
Strings that normalize to the empty string (no letters at all) form one group of their own.
Examples
Input: strs = ["Listen","Silent!","enlist","google","Go Ogle"] Output: [["Listen","Silent!","enlist"],["google","Go Ogle"]]
The first three normalize to the letters of listen; google and Go Ogle both normalize to google.
Input: strs = ["Dormitory","dirty room","cat","Act","tac."] Output: [["Dormitory","dirty room"],["cat","Act","tac."]]
Dormitory and dirty room use the same letters, as do the three spellings of cat.
Input: strs = ["abc","123","!!"] Output: [["abc"],["123","!!"]]
The two strings without letters normalize to the empty string and share a group.
Constraints
- 1 <= len(strs) <= 10^4
- 0 <= len(strs[i]) <= 100
- strs[i] consists of printable ASCII characters
Approaches
- Sorted normalized string as the key — time O(n · L log L), space O(n · L)
Follow-up
What if you only need how many pairs of strings are anagrams, or which strings have a partner at all? The same key answers both with counts instead of lists: see the use cases “Count the anagram pairs” and “Strings that have an anagram partner”.
Related problems
Start free on Cariara · Coding problems · System design studio
