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.