Programa C para verificar si dos strings dadas son isomorfas entre sí

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: 

  1. Inicialice dos arrays de tamaño 256.
  2. 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.
  3. Si no hay conflictos en el mapeo de los caracteres, imprima . 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;
}
Producción: 

Yes

 

Complejidad temporal: O(N) 
Espacio auxiliar: O(256)

Publicación traducida automáticamente

Artículo escrito por dmlalwani y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *