Table of Contents

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