You have been given two strings, 'str1' and 'str2'.
Your task is to return true if the given two strings are isomorphic to each other, else return false.
Two strings are isomorphic if a one-to-one mapping is possible for every character of the first string ‘str1’ to every character of the second string ‘str2’ while preserving the order of the characters.
All occurrences of every character in the first string ‘str1’ should map to the same character in the second string, ‘str2’.
If str1 = “aab” and str2 = “xxy” then the output will be 1. ‘a’ maps to ‘x’ and ‘b’ maps to ‘y’.
If str1 = “aab” and str2 = “xyz” then the output will be 0. There are two different characters in 'str1', while there are three different characters in 'str2'. So there won't be one to one mapping between 'str1' and 'str2'.
The first line contains the strings 'str1' and the next line contains the string 'str2'.
Print 1 if the two strings are isomorphic, else print 0.
aab
xxy
1
The character ‘a’ maps to ‘x’ and ‘b’ maps to ‘y’. Hence, the answer is 1 in this case.
aab
xyz
0
1 <= |str1|, |str2| <= 10^3
|str1| is the length of the string str1, and |str2| is the length of the string str2.
Can you solve this in O(N) time?
Think about mapping every character of str1 to str2.
The basic idea is to iterate through all the characters of str2 for every character of str1.
The steps are as follows:
O(N^2), where ‘N’ is the length of the strings.
Since we are traversing through the string “str1” for each character of “str1”, the overall time complexity will be O(N^2).
O(1).
Constant extra space is required. Hence, the overall space complexity is O(1).
All tags
Sort by
Interview problems
Python Solution
def areIsomorphic(str1: str, str2: str) -> bool:
# Write your code here
mp = {}
if len(str1) > len(str2):
return 0
for i in range(len(str1)):
curr = mp.get(str1[i],0)
# print(mp)
if curr == 0:
if str2[i] not in mp.values():
mp[str1[i]] = str2[i]
else:
return 0
else:
if str2[i] == mp[str1[i]]:
continue
else:
return 0
return 1
Interview problems
C++ unordered_map
#include<bits/stdc++.h> bool areIsomorphic(string &str1, string &str2) {
if(str1.length() != str2.length())return false;
unordered_map<char,char> mp1;
unordered_map<char,char> mp2;
for(int i = 0; i<str1.length(); i++){
char ch1 = str1[i];
char ch2 = str2[i];
if(mp1.find(ch1) != mp1.end()){
if(mp1[ch1] != ch2)return false;
}else{
mp1[ch1] = ch2;
}
if(mp2.find(ch2) != mp2.end()){
if(mp2[ch2] != ch1)return false;
}else{
mp2[ch2] = ch1;
}
}
return true;
}
Interview problems
C++
vector<int> str1Index(200, 0);
vector<int> str2Index(200, 0);
int len = str1.size();
if(str1.size() != str2.size()) {
return 0;
}
for(int i=0; i<len; i++) {
if(str1Index[str1[i]] != str2Index[str2[i]]) {
return 0;
}
str1Index[str1[i]]=i+1;
str2Index[str2[i]]=i+1;
}
return 1;
Interview problems
Easy Cpp Solution without using Map in O(N).
bool areIsomorphic(string &str1, string &str2)
{
string done = "";
done += str2[0]; // Append the first character of str2 to done
string visitstr1 = "";
visitstr1 += str1[0]; // Append the first character of str1 to visitstr1 (maintains visited characters)
if (str1.length() != str2.length()) {
return false; // Lengths are different, not isomorphic
}
for (int i = 1; i < str1.length(); i++) {
if (visitstr1.find(str1[i]) != string::npos) {
if (done.find(str2[i]) == string::npos) {
return false; // The character is already visited in str1 but received a different character in str2
}
}
else {
if (done.find(str2[i]) != string::npos) {
return false; // Received the same character which is already assigned to a character of str1
}
else {
done += str2[i]; // Received a different character in str2 for the respective character in str1
}
}
visitstr1 += str1[i]; // Add character str1[i] to visitstr1 as visited }
return true; // Strings are isomorphic
}
Interview problems
Unique Java Solution using array only
public class Solution {
public static boolean areIsomorphic(String str1, String str2) {
int one=str1.length();
int two=str2.length();
int[] arr=new int[123];
int[] lst=new int[123];
if(one!=two) return false;
int i=0;
while(i<one){
int key=(int) str1.charAt(i);
int val=(int) str2.charAt(i);
if(arr[key]!=0 || lst[val]!=0){
if(arr[key]==val && lst[val]==key) i++;
else return false;
}
else{
arr[key]=val;
lst[val]=key;
i++;
}
}
return true;
}
}
Interview problems
Best Java solution till I have seen
public static boolean areIsomorphic(String str1, String str2) {
if(str1.length() != str2.length()) return false;
int arr1[] = new int[26];
boolean arr2[] = new boolean[26];
for(int i=0; i<str1.length(); i++){
if(arr1[str1.charAt(i)-'a'] == 0 && arr2[str2.charAt(i)-'a'] == false){
arr1[str1.charAt(i)-'a'] = str2.charAt(i);
arr2[str2.charAt(i)-'a'] = true;
}else if(arr1[str1.charAt(i)-'a'] != str2.charAt(i)){
return false;
}
}
return true;
}Interview problems
Java Solution 50/50 test cases passed
class Solution {
public static boolean areIsomorphic(String str1, String str2) {
int map1[]=new int[200];
int map2[]=new int[200];
if(str1.length()!=str2.length())
return false;
for(int i=0;i<str1.length();i++)
{
if(map1[str1.charAt(i)]!=map2[str2.charAt(i)])
return false;
map1[str1.charAt(i)]=i+1;
map2[str2.charAt(i)]=i+1;
}
return true;
}
}
Interview problems
JAVA SOLUTION
public static boolean areIsomorphic(String str1, String str2) {
int first[]= new int[26];
int sec[]= new int[26];
if(str1.length()!=str2.length()) return false;
for(int i=0;i<str1.length();i++){
char a=str1.charAt(i);
char b=str2.charAt(i);
if((first[a-'a']!=0 && sec[b-'a']==0)||(first[a-'a']==0 && sec[b-'a']!=0)) return false;
else if(first[a-'a']==0 && sec[b-'a']==0){
first[a-'a']=1;
sec[b-'a']=1;
}
}
return true;
}
Interview problems
Cpp Easy to understand for begineer
#include<bits/stdc++.h>
bool areIsomorphic(string &str1, string &str2)
{
if(str1.length()!=str2.length()){
return false;
}
map<char,char>mp1;
map<char,char>mp2;
//let us keep str1 as key and str2 as value
//also here keep str2 as key and str1 as value
//as both are uniquely needed
//therefore we use two maps
for(int i=0;i<str1.length();i++){
if(mp1.find(str1[i])==mp1.end()){
mp1[str1[i]]=str2[i];
}
else{
if(mp1[str1[i]]!=str2[i]){
return false;
}
}
if(mp2.find(str2[i])==mp2.end()){
mp2[str2[i]]=str1[i];
}
else{
if(mp2[str2[i]]!=str1[i]){
return false;
}
}
}
return true;
}
Interview problems
easy python solution
def areIsomorphic(str1: str, str2: str) -> bool:
if len(str1)!=len(str2):
return 0
dict={}
for i in range(len(str2)):
if str1[i] not in dict:
if str2[i] in dict.values():
return (0)
else:
dict[str1[i]]=str2[i]
else:
if str2[i] not in dict.values():
return (0)
return (1)
# Write your code here
pass
