Dada una serie de palabras, imprima todos los anagramas juntos. Por ejemplo, si la array dada es {“gato”, “perro”, “tac”, “dios”, “acto”}, entonces la salida puede ser “gato tac acto perro dios”.
Un método simple es crear una tabla hash. Calcula el valor hash de cada palabra de tal manera que todos los anagramas tengan el mismo valor hash. Rellene la tabla hash con estos valores hash. Finalmente, imprima esas palabras junto con los mismos valores hash. Un mecanismo hash simple puede ser la suma módulo de todos los caracteres. Con módulo suma, dos palabras que no son anagramas pueden tener el mismo valor hash. Esto se puede manejar haciendo coincidir caracteres individuales.
El siguiente es otro método para imprimir todos los anagramas juntos. Tome dos arrays auxiliares, array de índice y array de palabras. Rellene la array de palabras con la secuencia de palabras dada. Ordene cada palabra individual de la array de palabras. Finalmente, ordene la array de palabras y realice un seguimiento de los índices correspondientes. Después de ordenar, todos los anagramas se agrupan. Utilice la array de índice para imprimir las strings de la array de strings original.
Entendamos los pasos con la siguiente Secuencia de palabras de entrada:
"cat", "dog", "tac", "god", "act"
1) Cree dos arrays auxiliares index[] y words[]. Copie todas las palabras dadas en palabras[] y almacene los índices originales en index[]
index[]: 0 1 2 3 4 words[]: cat dog tac god act
2) Ordenar palabras individuales en palabras[]. La array de índice no cambia.
index[]: 0 1 2 3 4 words[]: act dgo act dgo act
3) Ordenar la array de palabras. Compara palabras individuales usando strcmp() para ordenar
index: 0 2 4 1 3 words[]: act act act dgo dgo
4) Todos los anagramas vienen juntos. Pero las palabras se cambian en la array de palabras. Para imprimir las palabras originales, tome el índice de la array de índices y utilícelo en la array original. Obtenemos
"cat tac act dog god"
Las siguientes son las implementaciones del algoritmo anterior. En el siguiente programa, se utiliza una array de estructura «Palabra» para almacenar arrays de índices y palabras. Dupray es otra estructura que almacena una array de estructura «Palabra».
C++
// A C++ program to print all anagrams together
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
// structure for each word of duplicate array
class Word {
public:
char* str; // to store word itself
int index; // index of the word in the original array
};
// structure to represent duplicate array.
class DupArray {
public:
Word* array; // Array of words
int size; // Size of array
};
// Create a DupArray object that contains an array of Words
DupArray* createDupArray(char* str[], int size)
{
// Allocate memory for dupArray and all members of it
DupArray* dupArray = new DupArray();
dupArray->size = size;
dupArray->array
= new Word[(dupArray->size * sizeof(Word))];
// One by one copy words from the given wordArray to
// dupArray
int i;
for (i = 0; i < size; ++i) {
dupArray->array[i].index = i;
dupArray->array[i].str
= new char[(strlen(str[i]) + 1)];
strcpy(dupArray->array[i].str, str[i]);
}
return dupArray;
}
// Compare two characters. Used in qsort() for
// sorting an array of characters (Word)
int compChar(const void* a, const void* b)
{
return *(char*)a - *(char*)b;
}
// Compare two words. Used in qsort()
// for sorting an array of words
int compStr(const void* a, const void* b)
{
Word* a1 = (Word*)a;
Word* b1 = (Word*)b;
return strcmp(a1->str, b1->str);
}
// Given a list of words in wordArr[],
void printAnagramsTogether(char* wordArr[], int size)
{
// Step 1: Create a copy of all words present in given
// wordArr. The copy will also have original indexes of
// words
DupArray* dupArray = createDupArray(wordArr, size);
// Step 2: Iterate through all words in dupArray and
// sort individual words.
int i;
for (i = 0; i < size; ++i)
qsort(dupArray->array[i].str,
strlen(dupArray->array[i].str), sizeof(char),
compChar);
// Step 3: Now sort the array of words in dupArray
qsort(dupArray->array, size, sizeof(dupArray->array[0]),
compStr);
// Step 4: Now all words in dupArray are together, but
// these words are changed. Use the index member of word
// struct to get the corresponding original word
for (i = 0; i < size; ++i)
cout << wordArr[dupArray->array[i].index] << " ";
}
// Driver program to test above functions
int main()
{
char* wordArr[] = { "cat", "dog", "tac", "god", "act" };
int size = sizeof(wordArr) / sizeof(wordArr[0]);
printAnagramsTogether(wordArr, size);
return 0;
}
// This is code is contributed by rathbhupendra
C
// A C program to print all anagrams together
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// structure for each word of duplicate array
struct Word {
char* str; // to store word itself
int index; // index of the word in the original array
};
// structure to represent duplicate array.
struct DupArray {
struct Word* array; // Array of words
int size; // Size of array
};
// Create a DupArray object that contains an array of Words
struct DupArray* createDupArray(char* str[], int size)
{
// Allocate memory for dupArray and all members of it
struct DupArray* dupArray
= (struct DupArray*)malloc(sizeof(struct DupArray));
dupArray->size = size;
dupArray->array = (struct Word*)malloc(
dupArray->size * sizeof(struct Word));
// One by one copy words from the given wordArray to
// dupArray
int i;
for (i = 0; i < size; ++i) {
dupArray->array[i].index = i;
dupArray->array[i].str
= (char*)malloc(strlen(str[i]) + 1);
strcpy(dupArray->array[i].str, str[i]);
}
return dupArray;
}
// Compare two characters. Used in qsort() for sorting an
// array of characters (Word)
int compChar(const void* a, const void* b)
{
return *(char*)a - *(char*)b;
}
// Compare two words. Used in qsort() for sorting an array
// of words
int compStr(const void* a, const void* b)
{
struct Word* a1 = (struct Word*)a;
struct Word* b1 = (struct Word*)b;
return strcmp(a1->str, b1->str);
}
// Given a list of words in wordArr[],
void printAnagramsTogether(char* wordArr[], int size)
{
// Step 1: Create a copy of all words present in given
// wordArr. The copy will also have original indexes of
// words
struct DupArray* dupArray
= createDupArray(wordArr, size);
// Step 2: Iterate through all words in dupArray and
// sort individual words.
int i;
for (i = 0; i < size; ++i)
qsort(dupArray->array[i].str,
strlen(dupArray->array[i].str), sizeof(char),
compChar);
// Step 3: Now sort the array of words in dupArray
qsort(dupArray->array, size, sizeof(dupArray->array[0]),
compStr);
// Step 4: Now all words in dupArray are together, but
// these words are changed. Use the index member of word
// struct to get the corresponding original word
for (i = 0; i < size; ++i)
printf("%s ", wordArr[dupArray->array[i].index]);
}
// Driver program to test above functions
int main()
{
char* wordArr[] = { "cat", "dog", "tac", "god", "act" };
int size = sizeof(wordArr) / sizeof(wordArr[0]);
printAnagramsTogether(wordArr, size);
return 0;
}
Java
// A Java program to print all anagrams together
import java.util.Arrays;
import java.util.Comparator;
public class GFG {
// class for each word of duplicate array
static class Word {
String str; // to store word itself
int index; // index of the word in the
// original array
// constructor
Word(String str, int index)
{
this.str = str;
this.index = index;
}
}
// class to represent duplicate array.
static class DupArray {
Word[] array; // Array of words
int size; // Size of array
// constructor
public DupArray(String str[], int size)
{
this.size = size;
array = new Word[size];
// One by one copy words from the
// given wordArray to dupArray
int i;
for (i = 0; i < size; ++i) {
// create a word Object with the
// str[i] as str and index as i
array[i] = new Word(str[i], i);
}
}
}
// Compare two words. Used in Arrays.sort() for
// sorting an array of words
static class compStr implements Comparator<Word> {
public int compare(Word a, Word b)
{
return a.str.compareTo(b.str);
}
}
// Given a list of words in wordArr[],
static void printAnagramsTogether(String wordArr[],
int size)
{
// Step 1: Create a copy of all words present
// in given wordArr. The copy will also have
// original indexes of words
DupArray dupArray = new DupArray(wordArr, size);
// Step 2: Iterate through all words in
// dupArray and sort individual words.
int i;
for (i = 0; i < size; ++i) {
char[] char_arr
= dupArray.array[i].str.toCharArray();
Arrays.sort(char_arr);
dupArray.array[i].str = new String(char_arr);
}
// Step 3: Now sort the array of words in
// dupArray
Arrays.sort(dupArray.array, new compStr());
// Step 4: Now all words in dupArray are together,
// but these words are changed. Use the index
// member of word struct to get the corresponding
// original word
for (i = 0; i < size; ++i)
System.out.print(
wordArr[dupArray.array[i].index] + " ");
}
// Driver program to test above functions
public static void main(String args[])
{
String wordArr[]
= { "cat", "dog", "tac", "god", "act" };
int size = wordArr.length;
printAnagramsTogether(wordArr, size);
}
}
// This code is contributed by Sumit Ghosh
Python
# A Python program to print all anagrams together # structure for each word of duplicate array class Word(object): def __init__(self, string, index): self.string = string self.index = index # Create a DupArray object that contains an array # of Words def createDupArray(string, size): dupArray = [] # One by one copy words from the given wordArray # to dupArray for i in xrange(size): dupArray.append(Word(string[i], i)) return dupArray # Given a list of words in wordArr[] def printAnagramsTogether(wordArr, size): # Step 1: Create a copy of all words present in # given wordArr. # The copy will also have original indexes of words dupArray = createDupArray(wordArr, size) # Step 2: Iterate through all words in dupArray and sort # individual words. for i in xrange(size): dupArray[i].string = ''.join(sorted(dupArray[i].string)) # Step 3: Now sort the array of words in dupArray dupArray = sorted(dupArray, key=lambda k: k.string) # Step 4: Now all words in dupArray are together, but # these words are changed. Use the index member of word # struct to get the corresponding original word for word in dupArray: print wordArr[word.index], # Driver program wordArr = ["cat", "dog", "tac", "god", "act"] size = len(wordArr) printAnagramsTogether(wordArr, size) # This code is contributed by BHAVYA JAIN
Producción:
cat tac act dog god
Complejidad de tiempo: Deje que haya N palabras y cada palabra tenga un máximo de M caracteres. El límite superior es O(NMLogM + MNLogN).
El paso 2 toma tiempo O(NMLogM). Ordenar una palabra requiere un tiempo máximo de O(MLogM). Por lo tanto, ordenar N-palabras toma tiempo O (NMLogM). el paso 3 toma O(MNLogN) Ordenar una array de palabras toma comparaciones NLogN. Una comparación puede tomar un tiempo máximo de O(M). Entonces, el tiempo para ordenar una array de palabras será O (MNLogN).
El problema se puede resolver fácilmente con el uso de un vector de pares. El par será de string e int. La string requerirá almacenar la string de entrada e int requerirá almacenar sus índices respectivos.
aquí está la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
#include <strings.h>
using namespace std;
void createDuplicateArray(
vector<pair<string, int> >& dupArray,
vector<string>& wordAr, int size)
{
for (int i = 0; i < size; i++) {
dupArray.push_back(make_pair(wordAr[i], i));
// pair.first contains the input words and
// pair.second contains its index
}
}
void printAnagramsTogether(vector<string>& wordArr,
int size)
{
vector<pair<string, int> >
dupArray; // dupArray to store the word-index pair
createDuplicateArray(
dupArray, wordArr,
size); // making copy of all the words and their
// respective index
// Iterate through all words in dupArray and sort
// characters in each word.
int i;
for (i = 0; i < size; ++i) {
sort(dupArray[i].first.begin(),
dupArray[i].first.end());
}
// now sort the whole vector to get the identical words
// together
sort(dupArray.begin(), dupArray.end());
// now all the indentical words are together but we have
// lost the original form of string
// so through index stored in the word-index pair fetch
// the original word from main input
for (i = 0; i < size; ++i)
cout << wordArr[dupArray[i].second] << " ";
}
int main()
{
vector<string> wordArr
= { "cat", "dog", "tac", "god", "act" };
printAnagramsTogether(wordArr, wordArr.size());
return 0;
}
cat tac act dog god
Complejidad del tiempo :
Sea N-palabras y cada palabra tiene un máximo de M caracteres.
O(NMLogM + MNLogN).
Aquí, primero ordenamos cada palabra, usamos la palabra ordenada como clave y luego colocamos una palabra original en un mapa. El valor del mapa será una lista que contenga todas las palabras que tengan la misma palabra después de ordenar.
Por último, imprimiremos todos los valores del hashmap donde el tamaño de los valores será mayor que 1.
C++
// C++ program to print anagrams
// together using dictionary
#include <bits/stdc++.h>
using namespace std;
void printAnagrams(string arr[], int size)
{
unordered_map<string, vector<string> > map;
// Loop over all words
for (int i = 0; i < size; i++) {
// Convert to char array, sort and
// then re-convert to string
string word = arr[i];
char letters[word.size() + 1];
strcpy(letters, word.c_str());
sort(letters, letters + word.size() + 1);
string newWord = "";
for (int i = 0; i < word.size() + 1; i++) {
newWord += letters[i];
}
// Calculate hashcode of string
// after sorting
if (map.find(newWord) != map.end()) {
map[newWord].push_back(word);
}
else {
// This is the first time we are
// adding a word for a specific
// hashcode
vector<string> words;
words.push_back(word);
map[newWord] = words;
}
}
// Print all the values where size is > 1
// If you want to print non-anagrams,
// just print the values having size = 1
unordered_map<string, vector<string> >::iterator it;
for (it = map.begin(); it != map.end(); it++) {
vector<string> values = map[it->first];
if (values.size() > 1) {
cout << "[";
for (int i = 0; i < values.size() - 1; i++) {
cout << values[i] << ", ";
}
cout << values[values.size() - 1];
cout << "]";
}
}
}
// Driver code
int main()
{
string arr[] = { "cat", "dog", "tac", "god", "act" };
int size = sizeof(arr) / sizeof(arr[0]);
printAnagrams(arr, size);
return 0;
}
// This code is contributed by Ankit Garg
Java
// Java program to print anagrams
// together using dictionary
import java.util.*;
public class FindAnagrams {
private static void printAnagrams(String arr[])
{
HashMap<String, List<String> > map
= new HashMap<>();
// loop over all words
for (int i = 0; i < arr.length; i++) {
// convert to char array, sort and
// then re-convert to string
String word = arr[i];
char[] letters = word.toCharArray();
Arrays.sort(letters);
String newWord = new String(letters);
// calculate hashcode of string
// after sorting
if (map.containsKey(newWord)) {
map.get(newWord).add(word);
}
else {
// This is the first time we are
// adding a word for a specific
// hashcode
List<String> words = new ArrayList<>();
words.add(word);
map.put(newWord, words);
}
}
// print all the values where size is > 1
// If you want to print non-anagrams,
// just print the values having size = 1
for (String s : map.keySet()) {
List<String> values = map.get(s);
if (values.size() > 1) {
System.out.print(values);
}
}
}
public static void main(String[] args)
{
// Driver program
String arr[]
= { "cat", "dog", "tac", "god", "act" };
printAnagrams(arr);
}
}
Python3
from collections import defaultdict
def printAnagramsTogether(words):
groupedWords = defaultdict(list)
# Put all anagram words together in a dictionary
# where key is sorted word
for word in words:
groupedWords["".join(sorted(word))].append(word)
# Print all anagrams together
for group in groupedWords.values():
print(" ".join(group))
if __name__ == "__main__":
arr = ["cat", "dog", "tac", "god", "act"]
printAnagramsTogether(arr)
C#
// C# program to print anagrams
// together using dictionary
using System;
using System.Collections.Generic;
class GFG {
private static void printAnagrams(String[] arr)
{
Dictionary<String, List<String> > map
= new Dictionary<String, List<String> >();
// loop over all words
for (int i = 0; i < arr.Length; i++) {
// convert to char array, sort and
// then re-convert to string
String word = arr[i];
char[] letters = word.ToCharArray();
Array.Sort(letters);
String newWord = new String(letters);
// calculate hashcode of string
// after sorting
if (map.ContainsKey(newWord)) {
map[newWord].Add(word);
}
else {
// This is the first time we are
// adding a word for a specific
// hashcode
List<String> words = new List<String>();
words.Add(word);
map.Add(newWord, words);
}
}
// print all the values where size is > 1
// If you want to print non-anagrams,
// just print the values having size = 1
List<String> value = new List<String>();
foreach(KeyValuePair<String, List<String> > entry in
map)
{
value.Add(entry.Key);
}
int k = 0;
foreach(KeyValuePair<String, List<String> > entry in
map)
{
List<String> values = map[value[k++]];
if (values.Count > 1) {
Console.Write("[");
int len = 1;
foreach(String s in values)
{
Console.Write(s);
if (len++ < values.Count)
Console.Write(", ");
}
Console.Write("]");
}
}
}
// Driver Code
public static void Main(String[] args)
{
String[] arr
= { "cat", "dog", "tac", "god", "act" };
printAnagrams(arr);
}
}
// This code is contributed by Princi Singh
[dog, god][cat, tac, act]
Complejidad temporal : O(M+N).
Espacio auxiliar: O(M x N).
Producción :
[cat, tac, act][dog, god]
Solución HashMap con O(NM)
En el enfoque anterior, estábamos clasificando cada string para mantener una clave similar, pero eso cuesta más tiempo en este enfoque aprovechará otro hashmap para mantener la frecuencia de los caracteres que generarán la misma función hash para diferentes strings que tienen la misma frecuencia de caracteres.
Aquí, tomaremos HashMap<HashMap, ArrayList>, el hashmap interno contará la frecuencia de los caracteres de cada string y el HashMap externo verificará si ese hashmap está presente o no, si está presente, agregará esa string a la lista correspondiente .
C++
// C++ code to print all anagrams together
#include <bits/stdc++.h>
using namespace std;
void solver(vector<string> my_list)
{
// Inner hashmap counts frequency
// of characters in a string.
// Outer hashmap for if same
// frequency characters are present in
// in a string then it will add it to
// the vector.
map<map<char, int>, vector<string>> my_map;
// Loop over all words
for(string str : my_list)
{
// Counting the frequency of the
// characters present in a string
map<char, int> temp_map;
vector<string> temp_my_list;
for(int i = 0; i < str.length(); ++i)
{
++temp_map[str[i]];
}
// If the same frequency of characters
// are already present then add that
// string into that arraylist otherwise
// created a new arraylist and add that
// string
auto it = my_map.find(temp_map);
if (it != my_map.end())
{
it->second.push_back(str);
}
else
{
temp_my_list.push_back(str);
my_map.insert({ temp_map, temp_my_list });
}
}
// Stores the result in a vector
vector<vector<string>> result;
for(auto it = my_map.begin();
it != my_map.end(); ++it)
{
result.push_back(it->second);
}
for(int i = 0; i < result.size(); ++i)
{
cout << "[";
for(int j = 0; j < result[i].size(); ++j)
{
cout << result[i][j] << ", ";
}
cout << "]";
}
}
// Driver code
int main()
{
vector<string> my_list = { "cat", "dog", "ogd",
"god", "atc" };
solver(my_list);
return 0;
}
// This code is contributed by
// Apurba Kumar Gorai(coolapurba05)
Java
// Java code tp print all anagrams together
import java.util.ArrayList;
import java.util.HashMap;
public class FindAnagrams {
private static ArrayList<ArrayList<String> >
solver(
ArrayList<String> list)
{
// Inner hashmap counts frequency
// of characters in a string.
// Outer hashmap for if same
// frequency characters are present in
// in a string then it will add it to
// the arraylist.
HashMap<HashMap<Character, Integer>,
ArrayList<String> >
map = new HashMap<HashMap<Character, Integer>,
ArrayList<String> >();
for (String str : list) {
HashMap<Character, Integer>
tempMap = new HashMap<Character, Integer>();
// Counting the frequency of the
// characters present in a string
for (int i = 0; i < str.length(); i++) {
if (tempMap.containsKey(str.charAt(i))) {
int x = tempMap.get(str.charAt(i));
tempMap.put(str.charAt(i), ++x);
}
else {
tempMap.put(str.charAt(i), 1);
}
}
// If the same frequency of characters
// are already present then add that
// string into that arraylist otherwise
// created a new arraylist and add that string
if (map.containsKey(tempMap))
map.get(tempMap).add(str);
else {
ArrayList<String>
tempList = new ArrayList<String>();
tempList.add(str);
map.put(tempMap, tempList);
}
}
// Stores the result in a arraylist
ArrayList<ArrayList<String> >
result = new ArrayList<>();
for (HashMap<Character, Integer>
temp : map.keySet())
result.add(map.get(temp));
return result;
}
// Drivers Method
public static void main(String[] args)
{
ArrayList<String> list = new ArrayList<>();
list.add("cat");
list.add("dog");
list.add("ogd");
list.add("god");
list.add("atc");
System.out.println(solver(list));
}
}
// This code is contributed by Arijit Basu(ArijitXfx)
Python3
# Python code to print all anagrams together
from collections import Counter, defaultdict
user_input = ["cat", "dog", "tac", "edoc", "god", "tacact",
"act", "code", "deno", "node", "ocde", "done", "catcat"]
def solve(words: list) -> list:
# defaultdict will create a new list if the key is not found in the dictionary
m = defaultdict(list)
# loop over all the words
for word in words:
# Counter('cat') :
# counts the frequency of the characters present in a string
# >>> Counter({'c': 1, 'a': 1, 't': 1})
# frozenset(dict(Counter('cat')).items()) :
# frozenset takes an iterable object as input and makes them immutable.
# So that hash(frozenset(Counter('cat'))) is equal to
# hash of other 'cat' anagrams
# >>> frozenset({('c', 1), ('a', 1), ('t', 1)})
m[frozenset(dict(Counter(word)).items())].append(word)
return [v for k, v in m.items()]
print(solve(user_input))
# This code is contributed by
# Rohan Kumar(@r0hnx)
[cat, atc, ][dog, ogd, god, ]
Complejidad de tiempo: Deje que haya N palabras y cada palabra tenga un máximo de M caracteres. El límite superior es O(NM).
Complejidad espacial: Deje que haya N palabras y cada palabra tenga un máximo de M caracteres, por lo tanto, máx. espacio de almacenamiento para cada palabra con un máx. M caracteres serán O(M), por lo tanto, para un máximo de N palabras, será O(N*M). Por lo tanto, el límite superior es O(NM).
Este artículo es una contribución de Aarti_Rathi y le gustaría contribuir, también puede escribir un artículo usando write.geeksforgeeks.org o enviar su 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Dada una secuencia de palabras, imprime todos los anagramas juntos | Conjunto 2
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA