Table of Contents

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