Imprime todos los pares de anagramas en una array dada de strings

Dada una array de strings, encuentre todos los pares de anagramas en la array dada. 
Ejemplo:  

Input: arr[] =  {"geeksquiz", "geeksforgeeks", "abcd",
                 "forgeeksgeeks", "zuiqkeegs"};
Output: (geeksforgeeks, forgeeksgeeks), (geeksquiz, zuiqkeegs)

Podemos encontrar si dos strings son anagramas o no en tiempo lineal usando la array de conteo (vea el método 2 de this ). 
Una idea simple para encontrar si todos los pares de anagramas es ejecutar dos bucles anidados. El bucle exterior recoge todas las cuerdas una por una. El bucle interior comprueba si las strings restantes son anagramas de la string seleccionada por el bucle exterior. 
A continuación se muestra la implementación de este enfoque: 

#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
 
/* function to check whether two strings are anagram of each other */
bool areAnagram(string str1, string str2)
{
    // Create two count arrays and initialize all values as 0
    int count[NO_OF_CHARS] = {0};
    int i;
 
    // For each character in input strings, increment count in
    // the corresponding count array
    for (i = 0; str1[i] && str2[i];  i++)
    {
        count[str1[i]]++;
        count[str2[i]]--;
    }
 
    // If both strings are of different length. Removing this condition
    // will make the program fail for strings like "aaca" and "aca"
    if (str1[i] || str2[i])
      return false;
 
    // See if there is any non-zero value in count array
    for (i = 0; i < NO_OF_CHARS; i++)
        if (count[i])
            return false;
     return true;
}
 
// This function prints all anagram pairs in a given array of strings
void findAllAnagrams(string arr[], int n)
{
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (areAnagram(arr[i], arr[j]))
                cout << arr[i] << " is anagram of " << arr[j] << endl;
}
 
 
/* Driver program to test to print printDups*/
int main()
{
    string arr[] = {"geeksquiz", "geeksforgeeks", "abcd",
                    "forgeeksgeeks", "zuiqkeegs"};
    int n = sizeof(arr)/sizeof(arr[0]);
    findAllAnagrams(arr, n);
    return 0;
}

// Java program to Print all pairs of
// anagrams in a given array of strings
public class GFG
{
    static final int NO_OF_CHARS = 256;
     
    /* function to check whether two
    strings are anagram of each other */
    static boolean areAnagram(String str1, String str2)
    {
        // Create two count arrays and initialize
        // all values as 0
        int[] count = new int[NO_OF_CHARS];
        int i;
 
        // For each character in input strings,
        // increment count in the corresponding
        // count array
        for (i = 0; i < str1.length() && i < str2.length();
                                                   i++)
        {
            count[str1.charAt(i)]++;
            count[str2.charAt(i)]--;
        }
 
        // If both strings are of different length.
        // Removing this condition will make the program
        // fail for strings like "aaca" and "aca"
        if (str1.length() != str2.length())
          return false;
 
        // See if there is any non-zero value in
        // count array
        for (i = 0; i < NO_OF_CHARS; i++)
            if (count[i] != 0)
                return false;
         return true;
    }
 
    // This function prints all anagram pairs in a
    // given array of strings
    static void findAllAnagrams(String arr[], int n)
    {
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++)
                if (areAnagram(arr[i], arr[j]))
                    System.out.println(arr[i] +
                       " is anagram of " + arr[j]);
    }
 
    /* Driver program to test to print printDups*/
    public static void main(String args[])
    {
        String arr[] = {"geeksquiz", "geeksforgeeks",
                        "abcd", "forgeeksgeeks",
                        "zuiqkeegs"};
        int n = arr.length;
        findAllAnagrams(arr, n);
    }
}
// This code is contributed by Sumit Ghosh

# Python3 program to find
# best meeting point in 2D array
NO_OF_CHARS = 256
 
# function to check whether two strings
# are anagram of each other
def areAnagram(str1: str, str2: str) -> bool:
 
    # Create two count arrays and
    # initialize all values as 0
    count = [0] * NO_OF_CHARS
    i = 0
 
    # For each character in input strings,
    # increment count in the corresponding
    # count array
    while i < len(str1) and i < len(str2):
        count[ord(str1[i])] += 1
        count[ord(str2[i])] -= 1
        i += 1
 
    # If both strings are of different length.
    # Removing this condition will make the program
    # fail for strings like "aaca" and "aca"
    if len(str1) != len(str2):
        return False
 
    # See if there is any non-zero value
    # in count array
    for i in range(NO_OF_CHARS):
        if count[i]:
            return False
        return True
 
# This function prints all anagram pairs
# in a given array of strings
def findAllAnagrams(arr: list, n: int):
    for i in range(n):
        for j in range(i + 1, n):
            if areAnagram(arr[i], arr[j]):
                print(arr[i], "is anagram of", arr[j])
 
# Driver Code
if __name__ == "__main__":
 
    arr = ["geeksquiz", "geeksforgeeks",
           "abcd", "forgeeksgeeks", "zuiqkeegs"]
    n = len(arr)
    findAllAnagrams(arr, n)
 
# This code is contributed by
# sanjeev2552

// C# program to Print all pairs of
// anagrams in a given array of strings
using System;
 
class GFG
{
    static int NO_OF_CHARS = 256;
     
    /* function to check whether two
    strings are anagram of each other */
    static bool areAnagram(String str1, String str2)
    {
        // Create two count arrays and initialize
        // all values as 0
        int[] count = new int[NO_OF_CHARS];
        int i;
 
        // For each character in input strings,
        // increment count in the corresponding
        // count array
        for (i = 0; i < str1.Length &&
                    i < str2.Length; i++)
        {
            count[str1[i]]++;
            count[str2[i]]--;
        }
 
        // If both strings are of different length.
        // Removing this condition will make the program
        // fail for strings like "aaca" and "aca"
        if (str1.Length != str2.Length)
        return false;
 
        // See if there is any non-zero value in
        // count array
        for (i = 0; i < NO_OF_CHARS; i++)
            if (count[i] != 0)
                return false;
        return true;
    }
 
    // This function prints all anagram pairs in a
    // given array of strings
    static void findAllAnagrams(String []arr, int n)
    {
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++)
                if (areAnagram(arr[i], arr[j]))
                    Console.WriteLine(arr[i] +
                    " is anagram of " + arr[j]);
    }
 
    /* Driver program to test to print printDups*/
    public static void Main()
    {
        String []arr = {"geeksquiz", "geeksforgeeks",
                        "abcd", "forgeeksgeeks",
                        "zuiqkeegs"};
        int n = arr.Length;
        findAllAnagrams(arr, n);
    }
}
 
// This code is contributed by nitin mittal

<script>
// JavaScript program to find
// best meeting point in 2D array
let NO_OF_CHARS = 256
 
// function to check whether two strings
// are anagram of each other
function areAnagram(str1, str2){
 
    // Create two count arrays and
    // initialize all values as 0
    let count = [];
    for(let i = 0;i< NO_OF_CHARS;i++)
        count[i] = 0;
    let i = 0;
 
    // For each character in input strings,
    // increment count in the corresponding
    // count array
    while(i < (str1).length && i < (str2).length){
        count[ord(str1[i])] += 1;
        count[ord(str2[i])] -= 1;
        i += 1;
    }
 
    // If both strings are of different length.
    // Removing this condition will make the program
    // fail for strings like "aaca" and "aca"
    if ( (str1).length !=  (str2).length)
        return false;
 
    // See if there is any non-zero value
    // in count array
    for(let i = 0; i < NO_OF_CHARS; i++){
        if (count[i])
            return false;
        return True;
     }
}
 
// This function prints all anagram pairs
// in a given array of strings
function findAllAnagrams(arr, n){
    for(let i = 0; i < n; i++){
        for(let j = i + 1; j < n; j++){
            if areAnagram(arr[i], arr[j])
                document.write(arr[i]+"is anagram of"+arr[j])
        }
    }
}
    // Driver Code
    let arr = ["geeksquiz", "geeksforgeeks",
           "abcd", "forgeeksgeeks", "zuiqkeegs"];
    let n = (arr).length;
    findAllAnagrams(arr, n);
 
// This code is contributed by Rohitsingh07052.
</script>

Producción:  

geeksquiz is anagram of zuiqkeegs
geeksforgeeks is anagram of forgeeksgeeks

La complejidad temporal de la solución anterior es O(n ² *m) donde n es el número de strings ym es la longitud máxima de una string.

Espacio Auxiliar: O(1) o O(256).
Optimizaciones: 
podemos optimizar la solución anterior utilizando los siguientes enfoques. 
1) Usando la clasificación: podemos ordenar una array de strings para que todos los anagramas se junten. Luego imprima todos los anagramas recorriendo linealmente la array ordenada. La complejidad de tiempo de esta solución es O(mnLogn) (estaríamos haciendo comparaciones O(nLogn) en la clasificación y una comparación tomaría O(m) tiempo)
2) Usando Hashing:Podemos construir una función hash como XOR o la suma de los valores ASCII de todos los caracteres de una string. Usando una función hash de este tipo, podemos construir una tabla hash. Mientras construimos la tabla hash, podemos verificar si un valor ya tiene hash. En caso afirmativo, podemos llamar a areAnagrams() para verificar si dos strings son realmente anagramas (Tenga en cuenta que xor o la suma de los valores ASCII no es suficiente, consulte el comentario de Kaushik Lele aquí )
Abhishek contribuye con este artículo. Escriba comentarios si encuentra algo incorrecto o desea compartir más información sobre el tema anterior.