programmingexercises (5 Part Series)
Background
Recently, I decided to solve some of the problems in leetcode.com for fun and practicing my java which I have not used in a while. I decided to document my thought process as I solve these problems. You can find some of the other solutions in the series table above this section.
Problem
Group Anagrams
Given a list of strings, return a list where all anagrams are grouped together.
Input: [ate, cat, tac, eat, mat, tea, tam, bat]
Output: [[ate, eat, tea] [cat, tac], [mat, tam], [bat]]
Note
A word is considered an anagram of another if it can be formed by rearranging all the letters of the first word.
Solution
Finding an anagram
There are a couple of ways to finding if a word is an anagram of another.
Sorted String
If you have two string bac
and cab
if you sort them, they both result in the same string abc
. Hence they are anagrams of each other.
Count of characters
With the same two strings bac
and cab
if you can count the number of characters in each one of the like { a: 1, b: 1, c: 1 }
and if these match, then they are anagrams of each other.
Grouping Anagrams
My first thought was that counting characters might not be straightforward. So I went with the sorted string approach.
The rough algorithm was:
 Initialize an empty map which will store
SortedString > List of original Strings

For every string in the list,
2.1 Sort the string
2.2 If there is an entry in the map for the string add current string to the list.
2.3 Create a new list with this element and add it to map.
Return a list of all values in the map.
This yields the following code:
Complexity
The complexity of this solution is O(n.m.logm)
where is n is the number of strings in the list and m is the average length of the strings in the list.
Note
After solving this, I went through the solutions in leetcode, and found that you can use the character count solution to get a better O(n.m)
solution. I will attempt that next.
Posted on Jun 4 by:
Discussion