Given two strings 's1' and 's2', the task is to check if these two strings are isomorphic to each other.
Two strings s1 and s2 are called isomorphic if there is a one-to-one mapping possible for every character of s1 to every character of s2 while preserving the order.
Note: All occurrences of every character in s1 should map to the same character in s2 and any character in s2 should not map to two different in s1.
Input: s1="zoo", s2="aas"
Output: false
Input: s1="wfca", s2="yssy"
Output: false
Input: s1="zhi", s2="kcz"
Output: true
Solutions
Method 1: Using Hashing
The idea is to maintain a Hash to store s1 to s2 character mapping.
In order to verify if the given strings are isomorphic, one of the following conditions should be true:
1) If the hash contains an entry for the character s1[i], the value should match s2[i]. (to make sure any character from s1 is always mapped to the same character in s2).
2) Otherwise, s2[i] should not be saved as a value. (to make sure no character from s2 is mapped to more than one character in s1).
Complexity
The time complexity of this solution is O(n+m) and space complexity is O(distinctCharacters([n,m])).