132. Anagram Families
A word-puzzle site wants to put words that are built from exactly the same letters into one family. Two words belong to the same family when one can be rearranged into the other, using every letter exactly once. You are given the list words of lower case words.
Return the families as a list of lists of words: every input word appears in exactly one family, and equal words that occur several times appear several times. The order of the families and the order of the words inside a family do not matter. Compute a canonical key for each word and group by the key instead of comparing every pair.
Example 1
- Input:
- words = ["rat","tar","art","cat","act","dog"]
- Output:
- [["rat","tar","art"],["cat","act"],["dog"]]
- Explanation:
rat, tar and art use the same letters, as do cat and act; dog stands alone, giving three families.
Example 2
- Input:
- words = ["pots","stop","tops","opts","post"]
- Output:
- [["pots","stop","tops","opts","post"]]
- Explanation:
All five words are rearrangements of the same four letters, so they form a single family.
Constraints
1 ≤ words.length ≤ 20000
1 ≤ words[i].length ≤ 10
words[i] contains only lower case English letters
How this problem is judged
- Answers
- Lists at every level may be in any order. Duplicates still count.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n * L log L)
- Space
- O(n * L)