Leetcode #49 — Group Anagrams (Java)

Hello everyone, today we’ll be looking at the Group Anagrams problem. This question is marked as “Medium” on Leetcode.

Anagrams are words that have the same set of characters but in a different order. Grouping anagrams is a common problem in computer science, and it can be solved using various algorithms. In this blog post, we will look at a Java solution for this problem.

Problem Statement

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Examples from Leetcode

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

markInput: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Solution:

Submission on Leetcode:

Solution Breakdown:

• Line 4: checks if the input array strs is null or empty. If it is, it returns an empty list.
• Line 8: A HashMap is used to store the result, where the key is a sorted word, and the value is a list of words that are anagrams of that word.
• Lines 10–20:
  - The for loop iterates over each word in the input array strs
  - Convert each word s into an array of characters: ca
  - Arrays.sort(ca) sorts the characters in the ca array in lexicographical order.
  - String.valueOf(ca) converts the sorted array of characters back into a string: key
  - The next if statement: if the map does not contain key then a we add a new key-value pair in the map, where key = key and and the value is a new empty list creating using new ArrayList<>() …. If the key key already exists in the map, the if statement evaluates to false, and the execution continues to the next line.
• Line 22: new ArrayList<>(map.values()) creates a new ArrayList and adds the values from the map to it. This creates a new list that contains all the lists of words that are anagrams of each other.

Time Complexity:

O(n * k log k), where n is the number of words in the input array strs, and k is the maximum length of a word. The sorting operation takes O(k log k) time, and it needs to be performed n times, so the total time complexity is O(n * klogk)

Space Complexity:

O(n * k), where n is the number of words in the input array strs, and k is the maximum length of a word. The space needed to store the result and intermediate data is O(n * k)