Check if two given Strings are Isomorphic to each other
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’.
We strongly recommend that you click here and practice it, before moving on to the solution.
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.
- If this character is seen first time in str1, then-current of str2 must have not appeared before.
Below is the implementation of the above idea :
// C++ program to check if two strings are isomorphic
#include <bits/stdc++.h>
using namespace std;
#define MAX_CHARS 256
// This function returns true if str1 and str2 are
// isomorphic
bool areIsomorphic(string str1, string str2)
{
int m = str1.length(), n = str2.length();
// Length of both strings must be same for one to one
// correspondence
if (m != n)
return false;
// To mark visited characters in str2
bool marked[MAX_CHARS] = { false };
// To store mapping of every character from str1 to
// that of str2. Initialize all entries of map as -1.
int map[MAX_CHARS];
memset(map, -1, sizeof(map));
// Process all characters one by one
for (int i = 0; i < n; i++) {
// If current character of str1 is seen first
// time in it.
if (map[str1[i]] == -1) {
// If current character of str2 is already
// seen, one to one mapping not possible
if (marked[str2[i]] == true)
return false;
// Mark current character of str2 as visited
marked[str2[i]] = true;
// Store mapping of current characters
map[str1[i]] = str2[i];
}
// If this is not first appearance of current
// character in str1, then check if previous
// appearance mapped to same character of str2
else if (map[str1[i]] != str2[i])
return false;
}
return true;
}
// Driver program
int main()
{
cout << (areIsomorphic("aab", "xxy") ? "True" : "False")
<< endl;
return 0;
}
// Java program to check if two strings are isomorphic
import java.io.*;
import java.util.*;
class Isomorphic {
static int size = 256;
// Function returns true if str1 and str2 are isomorphic
static String areIsomorphic(String str1, String str2)
{
int m = str1.length();
int n = str2.length();
// Length of both strings must be same for one to
// one correspondence
if (m != n)
return "False";
// To mark visited characters in str2
Boolean[] marked = new Boolean[size];
Arrays.fill(marked, Boolean.FALSE);
// To store mapping of every character from str1 to
// that of str2. Initialize all entries of map as
// -1.
int[] map = new int[size];
Arrays.fill(map, -1);
// Process all characters one by one
for (int i = 0; i < n; i++) {
// If current character of str1 is seen first
// time in it.
if (map[str1.charAt(i)] == -1) {
// If current character of str2 is already
// seen, one to one mapping not possible
if (marked[str2.charAt(i)] == true)
return "False";
// Mark current character of str2 as visited
marked[str2.charAt(i)] = true;
// Store mapping of current characters
map[str1.charAt(i)] = str2.charAt(i);
}
// If this is not first appearance of current
// character in str1, then check if previous
// appearance mapped to same character of str2
else if (map[str1.charAt(i)] != str2.charAt(i))
return "False";
}
return "True";
}
// driver program
public static void main(String[] args)
{
String res = areIsomorphic("aab", "xxy");
System.out.println(res);
}
}
# Python program to check if two strings are isomorphic
MAX_CHARS = 256
# This function returns true if str1 and str2 are isomorphic
def areIsomorphic(string1, string2):
m = len(string1)
n = len(string2)
# Length of both strings must be same for one to one
# correspondence
if m != n:
return False
# To mark visited characters in str2
marked = [False] * MAX_CHARS
# To store mapping of every character from str1 to
# that of str2. Initialize all entries of map as -1
map = [-1] * MAX_CHARS
# Process all characters one by one
for i in xrange(n):
# if current character of str1 is seen first
# time in it.
if map[ord(string1[i])] == -1:
# if current character of st2 is already
# seen, one to one mapping not possible
if marked[ord(string2[i])] == True:
return False
# Mark current character of str2 as visited
marked[ord(string2[i])] = True
# Store mapping of current characters
map[ord(string1[i])] = string2[i]
# If this is not first appearance of current
# character in str1, then check if previous
# appearance mapped to same character of str2
elif map[ord(string1[i])] != string2[i]:
return False
return True
# Driver program
print areIsomorphic("aab", "xxy")
# This code is contributed by Bhavya Jain
// C# program to check if two
// strings are isomorphic
using System;
class GFG {
static int size = 256;
// Function returns true if str1
// and str2 are isomorphic
static bool areIsomorphic(String str1, String str2)
{
int m = str1.Length;
int n = str2.Length;
// Length of both strings must be same
// for one to one correspondence
if (m != n)
return false;
// To mark visited characters in str2
bool[] marked = new bool[size];
for (int i = 0; i < size; i++)
marked[i] = false;
// To store mapping of every character
// from str1 to that of str2 and
// Initialize all entries of map as -1.
int[] map = new int[size];
for (int i = 0; i < size; i++)
map[i] = -1;
// Process all characters one by one
for (int i = 0; i < n; i++) {
// If current character of str1 is
// seen first time in it.
if (map[str1[i]] == -1) {
// If current character of str2
// is already seen, one to
// one mapping not possible
if (marked[str2[i]] == true)
return false;
// Mark current character of
// str2 as visited
marked[str2[i]] = true;
// Store mapping of current characters
map[str1[i]] = str2[i];
}
// If this is not first appearance of current
// character in str1, then check if previous
// appearance mapped to same character of str2
else if (map[str1[i]] != str2[i])
return false;
}
return true;
}
// Driver code
public static void Main()
{
bool res = areIsomorphic("aab", "xxy");
Console.WriteLine(res);
}
}
// This code is contributed by Sam007.
<script>
// Javascript program to check if two
// strings are isomorphic
let size = 256;
// Function returns true if str1
// and str2 are isomorphic
function areIsomorphic(str1, str2)
{
let m = str1.length;
let n = str2.length;
// Length of both strings must be same
// for one to one correspondence
if(m != n)
return false;
// To mark visited characters in str2
let marked = new Array(size);
for(let i = 0; i < size; i++)
marked[i]= false;
// To store mapping of every character
// from str1 to that of str2 and
// Initialize all entries of map as -1.
let map = new Array(size);
map.fill(0);
for(let i = 0; i < size; i++)
map[i]= -1;
// Process all characters one by one
for (let i = 0; i < n; i++)
{
// If current character of str1 is
// seen first time in it.
if (map[str1[i].charCodeAt()] == -1)
{
// If current character of str2
// is already seen, one to
// one mapping not possible
if (marked[str2[i].charCodeAt()] == true)
return false;
// Mark current character of
// str2 as visited
marked[str2[i].charCodeAt()] = true;
// Store mapping of current characters
map[str1[i].charCodeAt()] = str2[i].charCodeAt();
}
// If this is not first appearance of current
// character in str1, then check if previous
// appearance mapped to same character of str2
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);
// This code is contributed by decode2207.
</script>
Output
True
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
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
// This function returns true if str1 and str2 are isomorphic
bool areStringsIsomorphic(string str1, string str2) {
// Initializing an unordered_map to store character mappings from str1 to str2
unordered_map<char, char> charMapping;
// Iterating over str1 and str2
for (int i = 0; i < str1.length(); i++) {
// Check if the character in str1 at index i is already mapped
if (charMapping.count(str1[i])) {
// If the mapped value for str1[i] is not equal to str2[i], return false
if (charMapping[str1[i]] != str2[i]) {
return false;
}
} else {
// Check if the character in str2 at index i is already used in the mapping
vector<char> mappedCharacters;
for (const auto& pair : charMapping) {
mappedCharacters.push_back(pair.second);
}
if (find(mappedCharacters.begin(), mappedCharacters.end(), str2[i]) != mappedCharacters.end()) {
return false;
} else {
// Map str1[i] to str2[i]
charMapping[str1[i]] = str2[i];
}
}
}
return true;
}
int main() {
// Test strings
string inputString1 = "aac";
string inputString2 = "xxy";
// Check if the strings are isomorphic
if (inputString1.length() == inputString2.length() && areStringsIsomorphic(inputString1, inputString2)) {
cout << "True\n";
} else {
cout << "False\n";
}
return 0;
}
// Java program to check if two strings
// areIsomorphic
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;
}
/* Driver code*/
public static void main(String[] args)
{
String str1 = "aac";
String str2 = "xxy";
// Function Call
if (str1.length() == str2.length()
&& areIsomorphic(str1, str2))
System.out.println("True");
else
System.out.println("False");
}
}
// This code is contributed by phasing17
# Python3 program to check if two strings are IsIsomorphic
# this function returns true if str1
# and str2 are isomorphic
def areIsomorphic(str1, str2):
# initializing a dictionary
# to store letters from str1 and str2
# as key value pairs
charCount = dict()
# initially setting c to "a"
c = "a"
# iterating over str1 and str2
for i in range(len(str1)):
# if str1[i] is a key in charCount
if str1[i] in charCount:
c = charCount[str1[i]]
if c != str2[i]:
return False
# if str2[i] is not a value in charCount
elif str2[i] not in charCount.values():
charCount[str1[i]] = str2[i]
else:
return False
return True
# Driver Code
str1 = "aac"
str2 = "xxy"
# Function Call
if (len(str1) == len(str2) and areIsomorphic(str1, str2)):
print("True")
else:
print("False")
# this code is contributed by phasing17
// C# program to check if two strings
// areIsIsomorphic
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;
}
/* Driver code*/
public static void Main()
{
string str1 = "aac";
string str2 = "xxy";
// Function Call
if (str1.Length == str2.Length
&& areIsomorphic(str1.ToCharArray(),
str2.ToCharArray()))
Console.WriteLine("True");
else
Console.WriteLine("False");
Console.ReadLine();
}
}
<script>
// JavaScript program to check if two strings are IsIsomorphic
// this function returns true if str1
// and str2 are isomorphic
function areIsomorphic(str1, str2)
{
// initializing an object
// to store letters from str1 and str2
// as key value pairs
var charCount = {};
// initially setting c to "a"
var c = "a";
// iterating over str1 and str2
for (var i = 0; i < str1.length; i++)
{
// if str1[i] is a key in charCount
if (charCount.hasOwnProperty(str1[i]))
{
c = charCount[str1[i]];
if (c != str2[i])
return false;
}
// if str2[i] is not a value in charCount
else if (!Object.values(charCount).includes(str2[i]))
{
charCount[str1[i]] = str2[i];
}
else
return false;
}
return true;
}
// Driver Code
var str1 = "aac";
var str2 = "xxy";
// Function Call
if (str1.length == str2.length && areIsomorphic(str1, str2))
document.write(1);
else
document.write(0);
// This code is contributed by phasing17.
</script>
Output
True
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.
Contact Us