Leetcode Problem: Group Anagrams

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:

1. Initialize an empty map which will store SortedString -> List of original Strings

2. 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.

3. 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.