Last Updated: 6 Feb, 2021
Isomorphic Strings
Easy
Asked in companies
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.
Note :
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’.
For example :
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'.
Input format :
The first line contains the strings 'str1' and the next line contains the string 'str2'.
Output format :
Print 1 if the two strings are isomorphic, else print 0.
Approaches
The basic idea is to iterate through all the characters of str2 for every character of str1.
The steps are as follows:
- Start traversing string str1.
- For every character of string str1, iterate over string str2 and check if all occurrences of that character map to the same character in str2.
The idea is to create a Hash array to store mappings of processed characters of str1 and another array to mark visited characters of str2.
- If lengths of str1 and str2 are not the same, return false.
- Traverse both strings str1 and str2 simultaneously
- If the value of the current character of str1 is -1 in the hash array it means that the character is seen first time in it hence the current character of str2 must not have appeared before.
- If the current character of str2 is seen, then return false.
- Else mark the current character of str2 as visited and store it in the hash array and check if the previous occurrence of str1[i] mapped to the same character.
- If the value of the current character of str1 is -1 in the hash array it means that the character is seen first time in it hence the current character of str2 must not have appeared before.