Cómo verificar si 2 cadenas son anagramas en C

Cómo verificar si 2 cadenas son anagramas en lenguaje C

En este artículo, voy a discutir Cómo verificar si 2 cadenas son anagramas en lenguaje C con ejemplos. Lea nuestro artículo anterior donde discutimos Encontrar duplicados en una cadena usando operaciones bit a bit en lenguaje C con ejemplos.

Comprobando si 2 cadenas son anagramas en lenguaje C:

En este artículo, veremos cómo verificar si dos cadenas son anagramas o no. Primero, comprendamos qué se entiende por anagrama. Un anagrama son los dos conjuntos de cadenas que se forman utilizando el mismo conjunto de alfabetos.

Por ejemplo, aquí tenemos una palabra que es 'escucha' y se usan los mismos alfabetos en otras palabras que es 'silencio'. Entonces, estos son anagramas. Ahora tenemos que comprobar si dos cadenas son anagramas o no. Entonces, lo primero y más importante es verificar si dos cadenas tienen el mismo tamaño. Si son de diferentes tamaños, no pueden ser anagramas. Ahora, ¿cómo verificamos si las cadenas tienen el mismo conjunto de letras?

1 ^st Método para verificar si 2 cadenas son anagramas o no

Un enfoque simple toma el alfabeto desde el 1 ^st cadena y busca eso en el 2 ^do cadena.

Aquí encontramos 'l',

Ahora encontramos 'i',

Aquí encontramos 's',

Aquí encontramos 't',

Ahora hemos encontrado 'e',

Aquí encontramos 'n',

Ahora tenemos que dejar de escanear la primera cadena cuando llegamos a '\0'. De esta manera, hemos comparado todos los elementos y obtuvimos el resultado de que las dos cadenas dadas son anagramas. Si alguna de las letras de la 1 ^st la cadena no se encuentra en el 2 ^do string, entonces podemos decir que no son anagramas.

Entonces, ¿cuánto tiempo lleva este procedimiento?

Estamos comparando todas las letras del 1 ^st cadena con cada letra en el 2 ^do cadena, entonces esto es O (n ² ).

Complejidad de tiempo:O(n ² )

El procedimiento que le mostramos es el procedimiento más simple y toma n ² tiempo. Este es un procedimiento que requiere mucho tiempo. Una cosa más que tenemos que tener cuidado de que no haya duplicados en la cadena. No hemos tomado ningún alfabeto duplicado, si hay duplicados, entonces tenemos que lidiar con esa complejidad.

Entonces, ya hemos aprendido sobre el número de duplicados en una matriz. Esa misma lógica se aplicará aquí si hay duplicados en la cadena dada. Ahora echemos un vistazo a la 2 ^nd y el segundo método también estamos familiarizados con él, que utiliza una tabla hash.

2 ^do Método para verificar si 2 cadenas son anagramas o no

Hemos tomado una matriz 'H' de tamaño 26 porque el número total de alfabetos es 26, por eso estamos tomando esta matriz de tamaño. Y ya sabemos cómo usar una tabla hash como vemos en nuestros artículos anteriores.

Aquí estamos tomando todo el alfabeto en minúsculas. Si también queremos mayúsculas y caracteres especiales, tomaremos una matriz de tamaño 128. Pero como ejemplo, estamos tomando solo minúsculas, lo que significa que el tamaño de la tabla hash es 26.

Utilicemos una tabla hash para saber si dos cadenas son anagramas o no. Echemos un vistazo al procedimiento. En primer lugar, escribiremos los códigos ASCII de estos alfabetos en minúsculas.

Hemos escrito códigos ASCII de letras en la parte superior de la matriz 'A'. Escanee a través de esta cadena, usaremos un ciclo for que podemos ir a todos y cada uno de los alfabetos. Luego, para cada alfabeto, restaremos 97 del código ASCII de cada alfabeto,

Para 'l', 108 – 97 =11
Para 'i', 105 – 97 =8
Para 's', 115 – 97 =18
Para 't', 116 – 97 =19
Para 'e', ​​101 – 97 =4
Para 'n', 110 – 97 =13

Ahora, el procedimiento primero se resta 97 del código ASCII de un alfabeto en particular y luego se incrementa ese índice en 'H' que obtenemos de la resta. Como hicimos la resta anterior, ahora incrementa esos índices en 'H' uno por uno. Aquí le mostramos la matriz 'H' incrementada final como discutimos antes:

Este procedimiento ya lo hemos visto anteriormente para encontrar duplicados en cadenas. Entonces, vea que todos estos alfabetos son únicos. No hay duplicados. Supongamos que si algún carácter se repite, se incrementará y se convertirá en 2.

Ahora, ¿cuál es el siguiente paso? El siguiente paso es escanear a través del 2 ^do cadena y para cada carácter como hicimos anteriormente, reste 97 de cada código alfabético ASCII, y lo que sea que obtengamos de la resta, incremente ese índice en 'H' pero aquí disminuye el valor del índice en 'H'. Por ejemplo, nuestro 2 ^do la cadena es 'silenciosa',

Para 's', 115 – 97 =18
Para 'i', 105 – 97 =8
Para 'l', 108 – 97 =11
Para 'e', ​​101 – 97 =4
Para 'n', 110 – 97 =13
Para 't', 116 – 97 =19

Ahora tenemos que disminuir los índices anteriores en la matriz 'H'. Después de decrementar en 'H', obtendremos:

Vea que ningún índice debe convertirse en -1. Si se convierte en -1 significa que el alfabeto no está ahí. Entonces, podemos detenernos allí después de restar f se convierte en -1. Si nunca obtuvimos un valor de -1, significa que todos los caracteres están disponibles aquí. Entonces, estas dos cadenas son anagramas. Si obtenemos un -1, podemos detenernos ahí.

Entonces, este es el procedimiento usando una cadena, podemos mantener el conteo en la tabla hash, y con la segunda cadena, podemos seguir documentándolo si algún número se reduce a continuación 0 que se convierte en -1 significa que no se encuentra y podemos detenernos allí. Y de lo contrario, podemos buscar esta matriz una vez más y verificar que todos sean elementos 0. Si algo no es cero, puede detener e imprimir estos no son anagramas.

Ahora hagamos un análisis de cuánto tiempo tardamos en buscar cadenas.

Para escanear 1 ^st cadena, tarda n tiempo,

Para escanear 2 ^nd cadena, tomará n tiempo,

No estamos accediendo a toda la tabla hash; estamos accediendo a una ubicación en particular. Por lo tanto, podemos descuidar este tiempo, pero aquí dejemos que este tiempo sea n.

Complejidad de tiempo:O (n + n + n) =O (3n) =O (n)

Ahora veamos la parte del código.

Comprobando si 2 cadenas son código de anagrama en lenguaje C: