The Interview Question Today#19(14-3-19)

Question:

Check if two given strings are isomorphic to each other

Example:

Input:  String1 = "aab"
           String2 = "xxy"
Output: Given String Are Ismorphic ('a' is mapped to 'x' and 'b' is mapped to 'y'.)

Solution:

Approach:

1) If lengths of str1 and str2 are not same, return false.
2) Do following for every character in str1 and str2
   a) If this character is seen first time in str1, 
      then current of str2 must have not appeared before.
      (i) If current character of str2 is seen, return false.
          Mark current character of str2 as visited.
      (ii) Store mapping of current characters.
   b) Else check if previous occurrence of str1[i] mapped

      to same character.

C program:

#include<stdio.h>
#define MAX_CHARS 256
#include<string.h>

// This function returns true if str1 and str2 are ismorphic
int areIsomorphic(char *str1,char *str2)
{
int i;
for(i=0;str1[i]!='\0';i++);
int m=i;

for(i=0;str2[i]!='\0';i++);
int n=i;

    if (m != n)
      return 0;

    // To mark visited characters in str2
    int marked[MAX_CHARS] = {0};

    int map[MAX_CHARS];
    memset(map, -1, sizeof(map));

    for ( i = 0; i < n; i++)
    {
        if (map[str1[i]] == -1)
        {
            if (marked[str2[i]] == 1)
                return 0;

               marked[str2[i]] = 1;

            map[str1[i]] = str2[i];
        }

        else if (map[str1[i]] != str2[i])
            return 0;
    }

    return 1;

}

int main()
{
    char str1[100];
    char str2[100];
    printf("Enter the First String: ");
    scanf("%s",str1);
    printf("Enter the Second String: ");
    scanf("%s",str2);

    if(areIsomorphic(str1,str2))
   printf("Given String Are Ismorphic\n");
   else{
    printf("Given String Are Not Ismorphic\n");
   }
   return 0;
}

Output:
Enter the First String: aaa
Enter the Second String: xxx
Given String Are Ismorphic