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) {
map_str_anagrams.get(key).add(str);
} else {
List<String> list_anagram = new ArrayList<String>();
list_anagram.add(str);
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()) {
result.add(group);
}
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 ]