Dadas dos strings str1 y str2 , la tarea es verificar si las dos strings dadas son isomorfas entre sí o no .
Se dice que dos strings son isomorfas si existe un mapeo uno a uno posible para cada carácter de str1 a cada carácter de str2 y todas las apariciones de cada carácter en str1 se asignan al mismo carácter en str2 .
Ejemplos:
Entrada: str1 = “egg”, str2 = “add”
Salida: Sí
Explicación:
‘e’ en str1 con valor ASCII 101 se asigna a ‘a’ en str2 con valor ASCII 97.
‘g’ en str1 con valor ASCII 103 es asignado a ‘d’ en str2 con valor ASCII 100.Entrada: str1 = «huevos», str2 = «agregar»
Salida: No
Enfoque Hashing : consulte la publicación anterior para conocer elenfoque basado en Hashmap .
Complejidad temporal: O(N)
Espacio auxiliar: O(256)
Enfoque basado en valores ASCII : La idea es similar a la del enfoque anterior. Siga los pasos a continuación para resolver el problema:
- Inicialice dos arrays de tamaño 256.
- Iterar a través de los caracteres de las strings dadas e incrementar el índice igual al valor ASCII del carácter en la i- ésima posición.
- Si no hay conflictos en el mapeo de los caracteres, imprima Sí . De lo contrario, imprima No.
A continuación se muestra la implementación del enfoque anterior:
C
// C Program to implement // the above approach #include <stdio.h> #include <string.h> #include <stdbool.h> // Function to check and return if strings // str1 and str2 are isomorphic bool areIsomorphic(char *str1, char *str2) { // If the length of the strings // are not equal if (strlen(str1) != strlen(str2)) { return false; } // Initialise two arrays int arr1[256] = { 0 }, arr2[256] = { 0 }; // Traversing both the strings for (int i = 0; i < strlen(str1); i++) { // If current characters don't map if (arr1[(int)str1[i]] != arr2[(int)str2[i]]) { return false; } // Increment the count of characters // at their respective ASCII indices arr1[(int)str1[i]]++; arr2[(int)str2[i]]++; } return true; } // Driver Code int main() { char s1[] = "aab", s2[] = "xxy"; if (areIsomorphic(s1, s2)) printf("Yes\n"); else printf("No\n"); return 0; }
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(256)