Group Anagrams

Difficulty Level Medium
Frequently asked in Amazon Facebook Google Microsoft
Hashing StringViews 3132

We have to find out the group anagrams of the given words. This means for each word we are going to sort it and store it as a key and original input which is not sorted as a value and if any other input has the same value as a previously sorted string we are going to store at the same key, but with different value, for this, a vector is passed as an argument into out function in which we are going to do all the operations.

Anagrams: Words that are created by rearranging all the letters of another word are known as anagrams.

Example: Eat, ate, tea are anagrams of each other

In this problem, you are given some words. Your task is to arrange those words in a group which are anagrams of each other.

Example

Input: eat, tea, tan, ate, nat, bat

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

Algorithm

  1. Declare a map variable mymap, a vector <vector<string>> variable final_set.
  2. Inside a loop, take the input values in key and sort them
  3. Push back the value of input[ i ] to the key (which is a sorted string ) of the map.
  4. Using for-each pushback the value into the final set.
  5. Print the final set.

Explanation

At first, our input set in which all our input values are stored in passed as a parameter. Here we declare a map and vector of vectors variable of my_map and final_set  respectively. Coming in for loop which iterates the vector until the size of the vector is reached. In this loop, we are going to take the value of each index of input into a key.

The value store in the key we are going to sort it so that we can check it as an anagram, and place the value of input[ i ] into a key place of the map where the key is a sorted string. This will go on until we iterate all the values in the input set. And storing all the key value in the map,

Then we are going to add all the values of my_map into the final set vector of vectors. And finally, print it.

Example

Suppose input : [eat, tea,tan,ate,nat,bat]

Sorted key= aet

For aet as a key eat is going to store as a value

Again, the sorted key of tea is aet is going to store as a key and value as tea.

After doing all the iterations :

aet (Sorted string) : [eat, tea, ate]     //key-value pair

ant (Sorted string): [tan, ant]           //key-value pair

abt (Sorted string): [bat ]         //key-value pair

And at last, we get the output.

Implementation

C++ program for Group Anagrams

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;

vector<vector<string> > groupAnagrams(vector<string>& input_set)
{
    // the first value will hold the key,
    //the second vector is used to hold the multiple values.
    unordered_map<string, vector<string>> my_map;
    vector<vector<string> > final_set;

    for (int i = 0; i < input_set.size(); i++)
    {
        // take value at the index as a key
        string key = input_set[i];

        //sort the key
        sort(key.begin(), key.end());

        // add the value to that key
        my_map[key].push_back(input_set[i]);

    }

    for (auto n : my_map)
    {
        // add all the values in the map to the final set
        final_set.push_back(n.second);
    }

    return final_set;
}

int main()
{
    vector<string> input_set;
    input_set.push_back("eat");
    input_set.push_back("tea");
    input_set.push_back("tan");
    input_set.push_back("ate");
    input_set.push_back("nat");
    input_set.push_back("bat");

    vector<vector<string> > final_set =  groupAnagrams(input_set);

    // print the output
    cout<<" [ "<<endl;
    for (int i = 0; i < final_set.size(); i++)
    {
        if (final_set[i].size() > 0)
        {
            cout << "  [";
            for (int j = 0; j < final_set[i].size(); j++)
                cout<< final_set[i][j]<<" ";
            cout << "]";
        }
        cout<<endl;
    }
    cout<<" ] ";

    return 0;
}

[
 [bat ]
 [tan nat ]
 [eat tea ate ]
]

Java program for Group Anagrams

import java.util.*;
import java.util.stream.Collectors;

class findGroupAnagrams
{
  public static void getgroup(String[] words)
  {
    List<String> myList = Arrays.stream(words)
        .map(s -> s.toCharArray())
        .map(chars -> { Arrays.sort(chars); return new String(chars); })
        .collect(Collectors.toList());
    Map<String, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < myList.size(); i++)
    {
      map.putIfAbsent(myList.get(i), new ArrayList<>());
      map.get(myList.get(i)).add(i);
    }
    for (var entry: map.entrySet()) {
      System.out.println(entry.getValue().stream()
              .map(index -> words[index])
              .collect(Collectors.toList()));
    }
  }
  public static void main(String[] args)
  {
    String[] input = {"eat","tea","tan","ate","nat","bat"};
    getgroup(input);
  }
}

[eat, tea, ate]
[bat]
[tan, nat]

Complexity Analysis for Group Anagrams

Time Complexity

O(NM) where N is the number of words and M is the maximum character each word has.

Space Complexity

O(N+M) where N is the number of words and M is the maximum character each word has.

Translate »