Dada una secuencia de palabras, imprima todos los anagramas juntos usando STL

Dada una serie de palabras, imprima todos los anagramas juntos. 

Por ejemplo, 

Input: array = {“cat”, “dog”, “tac”, “god”, “act”}
output: cat tac act, dog god
Explanation: cat tac and act are anagrams 
and dog and god are anagrams as 
they have the same set of characters.

Input: array = {“abc”, “def”, “ghi”}
output: abc, def, ghi
Explanation: There are no anagrams in the array.

Otros enfoques se discuten aquí en estas publicaciones:  

• dada-una-secuencia-de-palabras-imprimir-todos-los-anagramas-juntos
• dada-una-secuencia-de-palabras-imprimir-todos-los-anagramas-juntos-set-2

Enfoque: esta es una solución de HashMap que utiliza la biblioteca de plantillas estándar de C++ que almacena el par clave-valor. En el hashmap, la clave será el conjunto ordenado de caracteres y el valor será la string de salida. Dos anagramas serán similares cuando se ordenen sus caracteres. Ahora,  

1. Almacene los elementos del vector en HashMap con la clave como string ordenada.
2. Si la clave es la misma, agregue la string al valor de HashMap (vector de string).
3. Atraviese el HashMap e imprima las strings de anagramas.

Implementación:

// C++ program for finding all anagram
// pairs in the given array
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
 
// Utility function for
// printing anagram list
void printAnagram(unordered_map<string,vector<string> >& store)
{
    for (auto it:store)
    {
        vector<string> temp_vec(it.second);
        int size = temp_vec.size();
       
        for (int i = 0; i < size; i++)
        cout << temp_vec[i] << " ";
           
        cout << "\n";
    }
}
 
// Utility function for storing
// the vector of strings into HashMap
void storeInMap(vector<string>& vec)
{
    unordered_map<string,vector<string> > store;
   
    for (int i = 0; i < vec.size(); i++)
    {
        string tempString(vec[i]);
       
          // sort the string
        sort(tempString.begin(),tempString.end());
       
          // make hash of a sorted string
        store[tempString].push_back(vec[i]);
    }
 
    // print utility function for printing
    // all the anagrams
    printAnagram(store);
}
 
// Driver code
int main()
{
    // initialize vector of strings
    vector<string> arr;
    arr.push_back("geeksquiz");
    arr.push_back("geeksforgeeks");
    arr.push_back("abcd");
    arr.push_back("forgeeksgeeks");
    arr.push_back("zuiqkeegs");
    arr.push_back("cat");
    arr.push_back("act");
    arr.push_back("tca");
 
    // utility function for storing
    // strings into hashmap
    storeInMap(arr);
    return 0;
}

# Python3 program for finding all anagram
# pairs in the given array
from collections import defaultdict
 
# Utility function for
# printing anagram list
def printAnagram(store: dict) -> None:
     
    for (k, v) in store.items():
        temp_vec = v
        size = len(temp_vec)
         
        if (size > 1):
            for i in range(size):
                print(temp_vec[i], end = " ")
                 
            print()
 
# Utility function for storing
# the vector of strings into HashMap
def storeInMap(vec: list) -> None:
 
    store = defaultdict(lambda: list)
     
    for i in range(len(vec)):
        tempString = vec[i]
        tempString = ''.join(sorted(tempString))
 
        # Check for sorted string
        # if it already exists
        if (tempString not in store):
            temp_vec = []
            temp_vec.append(vec[i])
            store[tempString] = temp_vec
 
        else:
             
            # Push new string to
            # already existing key
            temp_vec = store[tempString]
            temp_vec.append(vec[i])
            store[tempString] = temp_vec
 
    # Print utility function for
    # printing all the anagrams
    printAnagram(store)
 
# Driver code
if __name__ == "__main__":
 
    # Initialize vector of strings
    arr = []
    arr.append("geeksquiz")
    arr.append("geeksforgeeks")
    arr.append("abcd")
    arr.append("forgeeksgeeks")
    arr.append("zuiqkeegs")
    arr.append("cat")
    arr.append("act")
    arr.append("tca")
 
    # Utility function for storing
    # strings into hashmap
    storeInMap(arr)
 
# This code is contributed by sanjeev2552

cat act tca 
abcd 
geeksquiz zuiqkeegs 
geeksforgeeks forgeeksgeeks 

Nota: Compile el programa anterior con el indicador -std=c++11 en g++ 

Análisis de Complejidad: 

• Complejidad de tiempo: O(n * m(log m)) , donde m es la longitud de una palabra.
  Se necesita un solo recorrido a través de la array.
• Complejidad espacial: O(n). 
  Hay n palabras en una string. El mapa requiere espacio O(n) para almacenar las strings.

Este artículo es una contribución de Mandeep Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.