Two strings str1 and str2 are called isomorphic if there is a one-to-one mapping possible for every character of str1 to every character of str2. And all occurrences of every character in ‘str1’ map to the same character in ‘str2’.
Examples:
Input: str1 = “aab”, str2 = “xxy”
Output: True
Explanation: ‘a’ is mapped to ‘x’ and ‘b’ is mapped to ‘y’.
Input: str1 = “aab”, str2 = “xyz”
Output: False
Explanation: One occurrence of ‘a’ in str1 has ‘x’ in str2 and other occurrence of ‘a’ has ‘y’.
Naive Approach:
A Simple Solution is to consider every character of ‘str1’ and check if all occurrences of it map to the same character in ‘str2’.
Time Complexity: O(N * N)
Auxiliary Space: O(1)
Check if two given strings are isomorphic to each other using Mapping:
The idea is to create an array to store mappings of processed characters.
Follow the steps below to solve the problem:
- If the lengths of str1 and str2 are not same, return false.
- Do the following for every character in str1 and str2.
- If this character is seen first time in str1, then-current of str2 must have not appeared before.
- If the current character of str2 is seen, return false. Mark the current character of str2 as visited.
- Store mapping of current characters.
- Else check if the previous occurrence of str1[i] mapped to the same character.
Below is the implementation of the above idea :
C++
#include <bits/stdc++.h>
using namespace std;
#define MAX_CHARS 256
bool areIsomorphic(string str1, string str2)
{
int m = str1.length(), n = str2.length();
if (m != n)
return false ;
bool marked[MAX_CHARS] = { false };
int map[MAX_CHARS];
memset (map, -1, sizeof (map));
for ( int i = 0; i < n; i++) {
if (map[str1[i]] == -1) {
if (marked[str2[i]] == true )
return false ;
marked[str2[i]] = true ;
map[str1[i]] = str2[i];
}
else if (map[str1[i]] != str2[i])
return false ;
}
return true ;
}
int main()
{
cout << (areIsomorphic( "aab" , "xxy" ) ? "True" : "False" )
<< endl;
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class Isomorphic {
static int size = 256 ;
static String areIsomorphic(String str1, String str2)
{
int m = str1.length();
int n = str2.length();
if (m != n)
return "False" ;
Boolean[] marked = new Boolean[size];
Arrays.fill(marked, Boolean.FALSE);
int [] map = new int [size];
Arrays.fill(map, - 1 );
for ( int i = 0 ; i < n; i++) {
if (map[str1.charAt(i)] == - 1 ) {
if (marked[str2.charAt(i)] == true )
return "False" ;
marked[str2.charAt(i)] = true ;
map[str1.charAt(i)] = str2.charAt(i);
}
else if (map[str1.charAt(i)] != str2.charAt(i))
return "False" ;
}
return "True" ;
}
public static void main(String[] args)
{
String res = areIsomorphic( "aab" , "xxy" );
System.out.println(res);
}
}
|
Python
MAX_CHARS = 256
def areIsomorphic(string1, string2):
m = len (string1)
n = len (string2)
if m ! = n:
return False
marked = [ False ] * MAX_CHARS
map = [ - 1 ] * MAX_CHARS
for i in xrange (n):
if map [ ord (string1[i])] = = - 1 :
if marked[ ord (string2[i])] = = True :
return False
marked[ ord (string2[i])] = True
map [ ord (string1[i])] = string2[i]
elif map [ ord (string1[i])] ! = string2[i]:
return False
return True
print areIsomorphic( "aab" , "xxy" )
|
C#
using System;
class GFG {
static int size = 256;
static bool areIsomorphic(String str1, String str2)
{
int m = str1.Length;
int n = str2.Length;
if (m != n)
return false ;
bool [] marked = new bool [size];
for ( int i = 0; i < size; i++)
marked[i] = false ;
int [] map = new int [size];
for ( int i = 0; i < size; i++)
map[i] = -1;
for ( int i = 0; i < n; i++) {
if (map[str1[i]] == -1) {
if (marked[str2[i]] == true )
return false ;
marked[str2[i]] = true ;
map[str1[i]] = str2[i];
}
else if (map[str1[i]] != str2[i])
return false ;
}
return true ;
}
public static void Main()
{
bool res = areIsomorphic( "aab" , "xxy" );
Console.WriteLine(res);
}
}
|
Javascript
<script>
let size = 256;
function areIsomorphic(str1, str2)
{
let m = str1.length;
let n = str2.length;
if (m != n)
return false ;
let marked = new Array(size);
for (let i = 0; i < size; i++)
marked[i]= false ;
let map = new Array(size);
map.fill(0);
for (let i = 0; i < size; i++)
map[i]= -1;
for (let i = 0; i < n; i++)
{
if (map[str1[i].charCodeAt()] == -1)
{
if (marked[str2[i].charCodeAt()] == true )
return false ;
marked[str2[i].charCodeAt()] = true ;
map[str1[i].charCodeAt()] = str2[i].charCodeAt();
}
else if (map[str1[i].charCodeAt()] != str2[i].charCodeAt())
return 0;
}
return 1;
}
let res = areIsomorphic( "aab" , "xxy" );
document.write(res + "</br>" );
res = areIsomorphic( "aab" , "xyz" );
document.write(res);
</script>
|
Time Complexity: O(N), Traversing over the string of size N
Auxiliary Space: O(1)
Check if two given strings are isomorphic to each other using Single Hashmap:
The idea is to store map the character and check whether the mapping is correct or not
Follow the steps to solve the problem:
- Create a hashmap of (char, char) to store the mapping of str1 and str2.
- Now traverse on the string and check whether the current character is present in the Hashmap.
- If it is present then the character that is mapped is there at the ith index or not.
- Else check if str2[i] is not present in the key then add the new mapping.
- Else return false.
Below is the implementation of the above approach
C++
#include <bits/stdc++.h>
using namespace std;
bool areIsomorphic(string str1, string str2)
{
unordered_map< char , char > charCount;
for ( int i = 0; i < str1.length(); i++)
{
if (charCount.count(str1[i]))
{
if (charCount[str1[i]] != str2[i]) {
return false ;
}
}
else {
vector< char > values;
for ( auto it : charCount) {
values.push_back(it.second);
}
if (find(values.begin(), values.end(), str2[i])
!= values.end()) {
return false ;
}
else {
charCount[str1[i]] = str2[i];
}
}
}
return true ;
}
int main()
{
string str1 = "aac" ;
string str2 = "xxy" ;
if (str1.length() == str2.length()
&& areIsomorphic(str1, str2)) {
cout << "True\n" ;
}
else {
cout << "False\n" ;
}
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
static boolean areIsomorphic(String str1, String str2)
{
HashMap<Character, Character> charCount
= new HashMap();
char c = 'a' ;
for ( int i = 0 ; i < str1.length(); i++) {
if (charCount.containsKey(str1.charAt(i))) {
c = charCount.get(str1.charAt(i));
if (c != str2.charAt(i))
return false ;
}
else if (!charCount.containsValue(
str2.charAt(i))) {
charCount.put(str1.charAt(i),
str2.charAt(i));
}
else {
return false ;
}
}
return true ;
}
public static void main(String[] args)
{
String str1 = "aac" ;
String str2 = "xxy" ;
if (str1.length() == str2.length()
&& areIsomorphic(str1, str2))
System.out.println( "True" );
else
System.out.println( "False" );
}
}
|
Python3
def areIsomorphic(str1, str2):
charCount = dict ()
c = "a"
for i in range ( len (str1)):
if str1[i] in charCount:
c = charCount[str1[i]]
if c ! = str2[i]:
return False
elif str2[i] not in charCount.values():
charCount[str1[i]] = str2[i]
else :
return False
return True
str1 = "aac"
str2 = "xxy"
if ( len (str1) = = len (str2) and areIsomorphic(str1, str2)):
print ( "True" )
else :
print ( "False" )
|
C#
using System;
using System.Collections.Generic;
public class GFG {
static bool areIsomorphic( char [] str1, char [] str2)
{
Dictionary< char , char > charCount
= new Dictionary< char , char >();
char c = 'a' ;
for ( int i = 0; i < str1.Length; i++) {
if (charCount.ContainsKey(str1[i])
&& charCount.TryGetValue(str1[i], out c)) {
if (c != str2[i])
return false ;
}
else if (!charCount.ContainsValue(str2[i])) {
charCount.Add(str1[i], str2[i]);
}
else {
return false ;
}
}
return true ;
}
public static void Main()
{
string str1 = "aac" ;
string str2 = "xxy" ;
if (str1.Length == str2.Length
&& areIsomorphic(str1.ToCharArray(),
str2.ToCharArray()))
Console.WriteLine( "True" );
else
Console.WriteLine( "False" );
Console.ReadLine();
}
}
|
Javascript
<script>
function areIsomorphic(str1, str2)
{
var charCount = {};
var c = "a" ;
for ( var i = 0; i < str1.length; i++)
{
if (charCount.hasOwnProperty(str1[i]))
{
c = charCount[str1[i]];
if (c != str2[i])
return false ;
}
else if (!Object.values(charCount).includes(str2[i]))
{
charCount[str1[i]] = str2[i];
}
else
return false ;
}
return true ;
}
var str1 = "aac" ;
var str2 = "xxy" ;
if (str1.length == str2.length && areIsomorphic(str1, str2))
document.write(1);
else
document.write(0);
</script>
|
Time Complexity: O(N), traversing over the string of size N.
Auxiliary Space: O(1)
Thanks to Gaurav and Utkarsh for suggesting the above approach.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!