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) {
                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 ]


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.