Check if two given strings are isomorphic to each other

Given two strings s1 and s2, write a function that says whether the given strings are isomorphic or not. Two strings are said to be isomorphic if there is a one to one mapping between all characters in both strings

Example

INPUT
s1  = "aadc"
s2 =  "mmkl"

OUTPUT
TRUE

In the above example we can see that
'a' is mapped to 'm', 'd' is mapped to 'k' and 'c' is mapped to 'l'

Time Complexity : O(n)

Algorithm

1. Find the lengths of two strings s1 and s2, if the lengths are not same then return FALSE

2. Traverse both strings s1 and s2 similtaneously

    a) If the current character of s1 is seen first time in it, then current character of s2 must have     not appeared before.  
        (i) If current character of s2 is seen, then return false and mark current character of         s2 as visited.
        (ii) Store mapping of current characters.

    b) else, check if the previous occurence of s1[i] mapped to same character

C++ Program

#include<bits/stdc++.h>
#define NO_OF_CHARS 256
using namespace std;

 
// This function returns true if s1 and s2 are ismorphic
bool isIsomorphic(string s1, string s2)
{
 
    int m = s1.length(), n = s2.length();
 
    //if lengths are not same then they are not isomorphic
    if (m != n)
      return false;
 
    // To mark visited characters in s2
    bool is_visited[NO_OF_CHARS] = {false};
 
    // To store mapping of every character from s1 to
    // that of s2. Initialize all entries of map as -1.
    int map[NO_OF_CHARS];
    memset(map, -1, sizeof(map));
 
    // P
    for (int i = 0; i < n; i++)
    {
        // If current character of s1 is seen first
        // time in it.
        if (map[s1[i]] == -1)
        {
            // If current character of s2 is already
            // seen, one to one mapping not possible
            if (is_visited[s2[i]] == true)
                return false;
 
            // Mark current character of s2 as visited
            is_visited[s2[i]] = true;
 
            // Store mapping of current characters
            map[s1[i]] = s2[i];

        }
 
        //if this is not the first appearence of char in s1
        //then check its previous appearence is mapped to the
        //respective character
        else if (map[s1[i]] != s2[i])
            return false;
    }
 
    return true;
}
 
int main()
{
    string s1 = "aadc";
    string s2 = "mmkl";
   cout << isIsomorphic(s1, s2) << endl;
   return 0;
}
Try It

 


Next > < Prev
Scroll to Top