¿Cuál es el algoritmo más corto para probar si dos cadenas son anagramas?

Un anagrama es una reorganización de las letras de una palabra o frase a otra palabra o frase, usando todas las letras originales exactamente una vez.

Enfoque 1,

Tomaremos una matriz de recuento de longitud 26 porque cualquier palabra está compuesta por un total de 26 caracteres (puede aumentar la longitud de la matriz para adaptarse a caracteres especiales y símbolos, etc.)
(a, b, c … z).

int [] cuenta = nuevo int [26];

Para el carácter ‘a’ en una cadena, incrementaremos el recuento en los recuentos [0],
Para el carácter ‘b’ en una cadena, incrementaremos la cuenta en cuentas [1], y así sucesivamente.

¿Cómo identificaremos el índice de la matriz de conteo del personaje?

Código ASCII de a = 97
Código ASCII de b = 98
Código ASCII de c = 99
.
.
.
Código ASCII de z = 122

El primer carácter comienza desde ‘a’ que tiene el código ASCII 97, lo utilizaremos como base para identificar el índice en la matriz de conteo.
El índice para el carácter ‘a’ se calculará mediante (ASCII de ‘a’) – 97 = 97 – 97 = 0,
El índice para el carácter ‘b’ se calculará mediante (ASCII de ‘b’) – 97 = 98 – 97 = 1, y así sucesivamente.

Iterar de 0 a longitud de cadena,
Paso 1. para cada carácter en la cadena 1, incremente la cuenta en la posición respectiva en la matriz de cuentas.
Paso 2. para cada carácter en la cadena2, disminuya el conteo en la posición respectiva en la matriz de conteos.

Al final, si el recuento es 0 para las 26 posiciones en la matriz de recuento, los caracteres se equilibran en la cadena 1 y la cadena 2 y, de lo contrario, es ANAGRAMA entre sí.

Otro enfoque usando HashMap.

Paso 1. Cree un Hashmap donde la clave es el carácter y el valor es el recuento (número de veces que ocurre el carácter).
Paso 2. Itere la cadena 1, complete el hashmap e incremente el recuento de caracteres repetidos.
Paso 3. Itere la cadena 2, para cada carácter, verifique que el carácter esté presente en el mapa; si no, deténgase como no Anagrama. Si el personaje está presente, entonces disminuya la cuenta.
Además, elimine el elemento del hashmap si el recuento es 0.
Paso 4. Por último, si hashmap está vacío, las cadenas son anagrama, de lo contrario no.

Explicación detallada con el programa: Verifique si dos cadenas son Anagramas.

Este no es el más corto ni el más eficiente en memoria. Pero, creo que es realmente divertido.

Asigna un número primo a cada letra del alfabeto. Codifique las letras en dos palabras usando la asignación.

Multiplica las palabras codificadas. Cada anagrama debe tener un resultado único debido al “Teorema fundamental de la aritmética”. Si los resultados de dos multiplicaciones coinciden, has encontrado tu anagrama.

Ejemplo:
Tengamos dos palabras en nuestro alfabeto y hagamos la siguiente tarea.
a -> 2
b -> 3

aba -> codificar -> 232 -> multiplicar -> 12
baa -> codificar -> 322 -> multiplicar -> 12
Anagramas!

aab -> codificar -> 223 -> multiplicar -> 12
abb -> codificar -> 233 -> multiplicar -> 18
¡No anagramas!

Puede haber muchas formas de probarlo. Explicaré uno de ellos. Antes de abordar la solución, debe saber qué es un anagrama: Anagrama – Wikipedia. La primera condición debe ser ” ambas cadenas deben tener la misma longitud. “. Es una condición necesaria, si falla eso significa que no son anagramas. La segunda condición debe ser ” la frecuencia de cada carácter en la cadena1 debe ser la misma que la de la cadena2 “. Usando estas dos ideas, puede resolver este problema.

Complejidad del tiempo: O (n), que es bastante bueno.

#include
#include
#include usando el espacio de nombres estándar;
salida bool (cadena s1, cadena s2) {
if (s1.length ()! = s2.length ()) {// si la longitud no es igual, devuelve falso.
falso retorno;
}
int n = s1.length (); // ahora ambas cadenas tienen la misma longitud.
map mapBox1, mapBox2; // para almacenar la frecuencia de cada personaje.
for (int i = 0; i <26; i ++) {// frecuencia inicial
mapBox1 [i + 97] = 0;
mapBox2 [i + 97] = 0;
}
for (int i = 0; i mapBox1 [s1 [i]] ++;
mapBox2 [s2 [i]] ++;
}
for (char i = ‘a’; i <'z'; i ++) {// comprueba si la frecuencia del mismo carácter es la misma.
if (mapBox1 [i]! = mapBox2 [i]) {
falso retorno;
}
}
volver verdadero;

}
int main () {
cadena s1;
cadena s2;
cin >> s1 >> s2;
cout << salida (s1, s2) << endl;
devuelve 0;
}

Si ordena cualquiera de las matrices, la complejidad es o (nlog (n)), así que aquí hay otro enfoque:

booleano estático privado isAnagram (String str1, String str2) {

if (str1.length ()! = str2.length ())
falso retorno;

int [] partido = nuevo int [256];

Arrays.fill (visto, 0);
str1 = str1.toLowerCase ();
str2 = str2.toLowerCase ();

for (int i = 0; i match [str1.charAt (i)] = match [str1.charAt (i)] +1;
}

for (int i = 0; i if (visto [str2.charAt (i)] == 0)
falso retorno;
match [str2.charAt (i)] = match [str2.charAt (i)] – 1;
}

para (int i = 0; i <256; i ++) {
if (match [i]! = 0) devuelve falso;
}
volver verdadero;
}

Ordene la cadena y verifique que las cadenas ordenadas sean iguales o no.
Si es igual, entonces es un anagrama, de lo contrario no.

He usado el tipo de inserción. Puede utilizar un mejor algoritmo de ordenación, como la ordenación rápida o la ordenación por fusión.

Aquí está el código:

#include
#include
#include
insertionsort vacío (char a [100], int n);
vacío principal()
{
int t;
scanf (“% d”, & t);
mientras que (t–)
{
char a [100], b [100];
int n, m;
scanf (“% s”, a);
scanf (“% s”, b);
n = strlen (a);
m = strlen (b);
si (n! = m)
printf (“NO \ n”);
más
{
insertionsort (a, n);
inserciónort (b, m);
if (strcmp (a, b) == 0)
printf (“SÍ \ n”);
más
printf (“NO \ n”);
}
}
}
insertionsort vacío (char a [100], int n)
{
int i, agujero;
valor de char;
para (i = 1; i <= n-1; i ++)
{
valor = a [i];
hoyo = i;
while ((agujero> 0) && (un [agujero-1]> valor))
{
a [hoyo] = a [hoyo-1];
hoyo = hoyo-1;
}
un [agujero] = valor;
}
printf (“% s \ n”, a);
}

Haz un histograma alfabético para cada palabra. Si los histogramas coinciden exactamente, son anagramas. Tenga en cuenta que esto funciona para cualquier secuencia de letras, no solo para una palabra. Supongo que probablemente así es como sitios como Internet Anagram Server / I, Rearrangement Servant: anagram, anagrams, nag a ram, software, anagramme, anagrama, juego de palabras, juego de palabras, creador de anagramas, solucionador de anagramas, buscador de anagramas, generador de anagramas, anagrama fabricante, decodificador de anagramas, máquina de anagramas, crucigramas, transfigurar, pangramas, trabajos aleatorios. Probablemente van un paso más allá y hacen un CRC o hash en los datos del histograma para que puedan tener un número que represente un montón de frases diferentes, todas con el mismo conjunto de letras.

Obtenga la suma de ASCIIS de todos los caracteres en ambas cadenas, mientras ignora cualquier cosa que no sea un alfabeto ni http: //www.number. Puede que no sea tan corto pero sea un poco eficiente. Aquí hay un código c ++, diseñé para resolver este problema:-

#include
#include
#include
usando el espacio de nombres estándar;

nulo to_lower (string & x) {
int index = 0;
while (index {
if (isalpha (x [índice]))
x [índice] = tolower (x [índice]);

index ++;
}
}

bool is_num (letra char) {
letra de retorno> = ‘0’ && letra <= '9';
}

int main ()
{
string word1 = “faiq123, 123”;
string word2 = “qiaf123, 123”;
int ASCIISUM1 = 0;
int ASCIISUM2 = 0;
cadena X = palabra1;
cadena Y = palabra2;
to_lower (X);
to_lower (Y);
para (int i = 0; i {
if (X [i] && (isalpha (X [i]) || is_num (X [i])))
ASCIISUM1 + = X [i];

if (Y [i] && (isalpha (Y [i]) || is_num (Y [i])))
ASCIISUM2 + = Y [i];
}

cout << ASCIISUM1 << endl;
cout << ASCIISUM2 << endl;
if (ASCIISUM1 == ASCIISUM2)
cout << "Ambos son anagramas" << endl;
devuelve 0;
}

Aquí hay una función en JavaScript.

var isAnagram = function (prueba, original)
{
if (test.length! = original.length) devuelve falso;

var nullChar = String.fromCharCode (0);

// Crear matrices más fáciles de comparar (recorte y minúsculas)
var testArray = test.trim (). toLowerCase (). split (”);
var originalArray = original.trim (). toLowerCase (). split (”);

var coincide = originalArray.length;
para (var t en testArray)
para (var i = originalArray.length-1; i> = 0; i–)
{
// ¿Aparece el personaje en la matriz original?
if (originalArray [i] === testArray [t])
{
// Sí, bórralo.
originalArray [i] = nullChar;
emparejado–;
descanso;
}
}

// Si eliminamos todos los elementos en la matriz original, entonces tenemos un anagrama.
retorno (coincidente == 0);
};

Editado: Gracias a Magdalena Mbn por la sugerencia sobre cómo acelerarlo (30%). Más información sobre mis pruebas de velocidad en los comentarios.

Código de longitud puede ser bastante corto en Python. Aquí hay una solución basada en la clasificación:

def are_anagrams (s1, s2):
return sorted (s1.replace (”, ”)) == sorted (s2.replace (”, ”))

Aquí hay uno basado en conteo:

del contador de importación de colecciones
def are_anagrams (s1, s2):
return Counter (s1.replace (”, ”)) == Counter (s2.replace (”, ”))

Simplemente cree una tabla hash con claves que representen los alfabetos y valores que representen la cantidad de veces que se repite ese alfabeto en la cadena.
Luego compara tanto la tabla hash.
Me gustó el enfoque de usuario de Quora. 🙂

Idea: ordenar las cadenas respectivas y probar la igualdad.

En C ++, he hecho esto usando 97 caracteres no espaciales con algunos hacks. Reto a cualquiera a crear uno más corto:

////////////////////////////// Comienzo de personaje ////////////////// /////
#include
#define Z (a) std :: sort (begin (a), end (a));
#define S std :: string
int A (S a, S b) {
Z (a)
Z (b)
devuelve a == b;
}

////////////////////////////Fin///////////////////// //////////////////
usando el espacio de nombres estándar;
int main () {
cuerda a, b;
cin >> a >> b;
cout << A (a, b) << endl;
devuelve 0;
}

Brevedad (la menor cantidad de código para una tarea efectiva) en c ++ código razonable / legible:

#include
usando el espacio de nombres estándar;
bool isAnagram (cadena a, cadena b) {
ordenar (comenzar (a), finalizar (a));
sort (comienzo (b), final (b));
devuelve a == b;
}

int main () {
cuerda a, b;
cin >> a >> b;
cout << isAnagram (a, b) << endl;
devuelve 0;
}

Solo contaría las ocurrencias de cada carácter en cada cadena y compararía para ver si son iguales. Es útil almacenar eso en una tabla hash. Aquí hay una implementación en python:

cuenta de definición (diccionario, cadena):
para el carácter en cadena:
dictionary [character] = dictionary.pop (personaje, 0) + 1
diccionario de retorno

def is_anagram (cadena1, cadena2):
return count (string1) == count (string2)

Ordene las cadenas y compare o incluso puede contar los números de cada letra en las cadenas y comparar.

Ordene ambas cadenas y pruebe la igualdad.

Ordene ambas cadenas alfabéticamente y verifique si son equivalentes.