Coders Packet

Java Program to Group Anagrams

By CHATTETI.THARUN

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

PROBLEM STATEMENT

Given an array of strings strs, group the anagrams. 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.

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lower-case English letters.

SOLUTION:

Algorithm/Approach:

  • If 2 strings are an anagram, then the count of characters should match in both strings.
  • So, even if we sort them, they should match.
  • Construct a map, with the key as a sorted string and the values with the same characters.
  • Now values are in an ArrayList.
  • then, Iterate through the given string array.
  • For each string, sort the string and use it because the key for a map and the actual (unsorted) string will be worth it.
  • Now, all the strings which are anagrams will have an equivalent key within the map.
import java.util.*; 
class Solution
{
public static List < List < String >> groupAnagrams(String[] strs)
{
List < List < String >> result = new ArrayList < > ();
String strn[] = new String[strs.length];
for (int i = 0; i < strs.length; i++)
{
char chr[] = strs[i].toCharArray();
Arrays.sort(chr);
strn[i] = String.valueOf(chr);
}
HashMap < String, ArrayList < String >> hmap = new HashMap < String, ArrayList < String >> ();
for (int i = 0; i < strs.length; i++)
{
if(hmap.containsKey(strn[i]))
{
ArrayList < String > list = hmap.get(strn[i]);
list.add(strs[i]); hmap.put(strn[i], list);
}
else
{
ArrayList < String > list = new ArrayList < > ();
list.add(strs[i]);
hmap.put(strn[i], list);
result.add(list);
}
}
return result;
}
}

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

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

 

Download project

Reviews Report

Submitted by CHATTETI.THARUN (Tharun)

Download packets of source code on Coders Packet