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


s1  = “aadc”
s2 =  “mmkl”


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)


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

#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


Leave a Comment

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc


Abhishek was able to crack Microsoft after practicing questions from TutorialCup