Isomorphic Strings

Easy
0/40
Average time to solve is 15m
profile
Contributed by
110 upvotes
Asked in companies
BarclaysCGIVMware Inc

Problem statement

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'.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
aab 
xxy
Sample Output 1 :
1
Explanation of sample input 1:
The character ‘a’ maps to ‘x’ and ‘b’ maps to ‘y’. Hence, the answer is 1 in this case.
Sample Input 2 :
aab
xyz
Sample Output 2 :
0
Constraints :
1 <= |str1|, |str2| <= 10^3

|str1| is the length of the string str1, and |str2| is the length of the string str2.
Follow Up:
Can you solve this in O(N) time?
Hint

Think about mapping every character of str1 to str2.

Approaches (2)
Brute-Force

The basic idea is to iterate through all the characters of str2 for every character of str1.

 The steps are as follows:

  1. Start traversing string str1.
  2. 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.
Time Complexity

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).

Space Complexity

O(1).

 

Constant extra space is required. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Isomorphic Strings
Full screen
Console