Group anagrams
MediumStuck?
Show a hintHide the hint
Sort the letters of each word. Words that are anagrams give the same result, so use that as a key in a hash map.
The idea behind this problem
Next in this lesson
What two lists have in commonGiven a list of words, group together the ones that are anagrams of each other. Return how many groups there are.
Worked example#
For ["eat", "tea", "tan", "ate", "nat", "bat"], sort the letters of each word and use that as a label:
| word | sorted letters |
|---|---|
| eat | aet |
| tea | aet |
| tan | ant |
| ate | aet |
| nat | ant |
| bat | abt |
Three distinct labels, so three groups: eat, tea, ate and tan, nat and bat. The answer is 3.
The idea worth taking away: anagrams are exactly the words that share a sorted form, so the sorted form is a key you can group by.
Constraints#
1 <= number of words <= 10000- Each word is one or more lowercase letters, at most 100 long
Input
words is a count then that many words, one per line.
Output
The number of groups.
Examples
Input
6 eat tea tan ate nat bat
Output
3
eat/tea/ate share the letters aet, tan/nat share ant, and bat is alone.
Input
1 a
Output
1
One word is one group.
Input
3 abc bca cab
Output
1
All three are the same letters rearranged.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.