# 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 StringViews 1603

## 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.

Translate »