# Algorithm For Grouping Anagrams

Create a hashmap / dictionary of [ string, list / vector of strings ].
The key of the hashmap / dictionary would be the word whose characters are in sorted order.
The value of the keys in hashmap would be anagrams ( words with the exact same characters ).

Example : If we sort the characters in the words tea, ate and eat we get the word aet.
Thus, aet would be the key in the hashmap and [ tea, ate, eat ] would be the values.

Key Value
aet [ tea, ate, eat ]

Algorithm
For each word in the word list do
Sort the characters in the word and check if the sorted_word (key) exists in the hashmap / dictionary.
If the sorted_word exists in the hashmap / dictionary, then
Put the word in the list (value) corresponding to the sorted_word.
Else
Create a new entry in the hashmap / dictionary where the key is the sorted_word and value is a list containing [ word ].

Program to group all the anagrams in a given list of strings.

``````from typing import List # For annotations

class Anagrams :

def Group_Strings (self, list_strings : List[str]) -> List[List[str]] :

anagrams = {}

for word in list_strings :
word = word.strip()
hashkey = "".join(sorted(word))
if hashkey not in anagrams :
anagrams[hashkey] = []
anagrams[hashkey].append(word)

group = []
for value in anagrams.items() :
group.append(value[1])

return group

def main () :

list_strings = ["tea", "tan", "ate", "marine", "bat", "remain", "eat", "airmen", "nat", "silent", "listen"]

print("Given strings : " + str(list_strings))

a = Anagrams()
groups = a.Group_Strings (list_strings)
print("Grouped anagrams ...")

for item in groups :
print(str(item))

if __name__ == "__main__" :
main()
``````

Output

``````Given strings : ['tea', 'tan', 'ate', 'marine', 'bat', 'remain', 'eat', 'airmen', 'nat', 'silent', 'listen']
Grouped anagrams ...
['tea', 'ate', 'eat']
['tan', 'nat']
['marine', 'remain', 'airmen']
['bat']
['silent', 'listen']
``````
``````#include<iostream>
#include<map>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

vector<vector<string>> GroupAnagrams (vector<string>& vec_strings) {

map<string, vector<string>> map_str_anagrams;

for (const auto& str : vec_strings) {

string key(str);
// sorted string is the key in the map.
sort(key.begin(), key.end());

if (map_str_anagrams.find(key) != map_str_anagrams.end()) {
map_str_anagrams[key].push_back(str);
} else {
vector<string> vec_ana {str};
map_str_anagrams[key] = vec_ana;
}
}

vector<vector<string>> result;

for (const auto& group : map_str_anagrams) {
result.push_back (group.second);
}
return result;
}

int main() {

vector<string> vec_strings { "tea", "tan", "ate", "marine", "bat", "remain", "eat", "airmen", "nat" };

cout << "Given strings : ";
for (const auto& str : vec_strings) {
cout << str << " ";
} cout << endl;

vector< vector<string>> groups = GroupAnagrams(vec_strings);
cout << "Grouped anagrams ..." << endl;

for (const auto& grp : groups) {
cout << "[ ";
for (const auto& str : grp) {
cout << str << " ";
} cout << "]" << endl;
}
return 0;
}
``````

Output

``````Given strings : tea tan ate marine bat remain eat airmen nat
Grouped anagrams ...
[ bat ]
[ marine remain airmen ]
[ tea ate eat ]
[ tan nat ]
``````
``````import java.util.List;
import java.util.HashMap;
import java.util.Arrays;
import java.util.ArrayList;

class Anagrams {

List<List<String>> Group (String[] list_strings) {

HashMap<String, List<String>> map_str_anagrams = new HashMap<String, List<String>>();

for (String str : list_strings) {

char [] char_array = str.toCharArray();

// sorted string is the key in the map.
Arrays.sort(char_array);

String key = String.valueOf(char_array);

if (map_str_anagrams.get(key) != null) {
} else {
List<String> list_anagram = new ArrayList<String>();
map_str_anagrams.put(key, list_anagram);
}
}

List<List<String>> result = new ArrayList<List<String>>(map_str_anagrams.size());

for (List<String> group : map_str_anagrams.values()) {
}
return result;
}

public static void main (String[] args) {

String[] list_strings = {"tea", "tan", "ate", "marine", "bat", "remain", "eat", "airmen", "nat"};

System.out.print ("Given strings : ");
for (String str : list_strings) {
System.out.print (str + " ");
} System.out.println();

Anagrams a = new Anagrams();
List<List<String>> groups = a.Group(list_strings);
System.out.println("Grouped anagrams ...");

for (List<String> grp : groups) {
System.out.print ( "[ ");
for (String str : grp) {
System.out.print (str + " ");
} System.out.println ("]");
}
}
}
``````

Output

``````Given strings : tea tan ate marine bat remain eat airmen nat
Grouped anagrams ...
[ tea ate eat ]
[ bat ]
[ tan nat ]
[ marine remain airmen ]
``````