Check if Two given Strings are Isomorphic to each other


Difficulty Level Easy
Frequently asked in Accolite Adobe Amazon GE Healthcare Goldman Sachs InfoEdge Oracle UHG Optum
HashMap String

Problem Statement

In the “Check if Two given Strings are Isomorphic to each other” problem we have given two strings s1 and s2. Write a program that says whether the given strings are isomorphic or not.

Note: Two strings are said to be isomorphic if there is a one to one mapping between all characters in both strings.

Input Format

The first line containing a string s1.

The second line containing another string s2.

Output Format

Print “TRUE” if the given strings are isomorphic otherwise print “FASLE”.

Constraints

  • 1<=|s1|<=10^5
  • 1<=|s2|<=10^5
  • s1[i] must be a lower case English alphabet
  • s2[i] must be a lower case English alphabet

Example

aadc
mmkl
TRUE

Explanation: We can see that ‘a’ is mapped to ‘m’, ‘d’ is mapped to ‘k’ and ‘c’ is mapped to ‘l’. So given strings are isomorphic.

Algorithm to Check if Two given Strings are Isomorphic to each other

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

2. Traverse both strings s1 and s2 simultaneously

    a) If the current character of s1 is seen the first time in it, then-current the character of s2 must have not appeared before.

  • If the current character of s2 is seen, then return false and mark the current character of s2 as visited.
  • Store mapping of current characters.

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

Implementation

C++ Program to Check if Two given Strings are Isomorphic to each other

#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,s2;
   cin>>s1>>s2;
   if(isIsomorphic(s1, s2))
   {
       cout<<"TRUE"<<endl;
   }
   else
   {
       cout<<"FALSE"<<endl;
   }
   return 0;
}

Java Program to Check if Two given Strings are Isomorphic to each other

import java.util.Scanner;
class sum
{
    // This function returns true if s1 and s2 are ismorphic
    public static boolean 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
        boolean is_visited[] = new boolean[256];
        for(int i=0;i<256;i++)
        {
            is_visited[i]=false;
        }
        // To store mapping of every character from s1 to
        // that of s2. Initialize all entries of map as -1.
        int map[] = new int [256];
        for(int i=0;i<256;i++)
        {
            map[i]=-1;
        }
        // P
        for (int i = 0; i < n; i++)
        {
            // If current character of s1 is seen first
            // time in it.
            if (map[s1.charAt(i)] == -1)
            {
                // If current character of s2 is already
                // seen, one to one mapping not possible
                if (is_visited[s2.charAt(i)] == true)
                    return false;

                // Mark current character of s2 as visited
                is_visited[s2.charAt(i)] = true;

                // Store mapping of current characters
                map[s1.charAt(i)] = s2.charAt(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.charAt(i)] != s2.charAt(i))
                return false;
        }

        return true;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        String s1 = sr.next();
        String s2 = sr.next();
        if(isIsomorphic(s1,s2)==true)
        {
            System.out.println("TRUE");
        }
        else
        {
            System.out.println("FALSE");
        }
    }
    
}
abpanban
pjhpljpl
TRUE
abpanban
pppjhljl
FALSE

Complexity Analysis to Check if Two given Strings are Isomorphic to each other

Time Complexity

O(n) where n is the length of the given strings. Here we simply traverse one string and check for another string. For checking, we take constant time only.

Space Complexity

O(1) because we declare space of 256 size only. Here 256 is too less if we compare it with a large value of n. So, space complexity is contatant.