Table of contents
Intuition
In order to determine if two strings are isomorphic, you can check if you can replace every occurrence of the letter s
in one string with the corresponding letter t
in the other string, and vice versa. In other words, there should be a one-to-one mapping between the characters of the two strings.
Approach
Let's consider the strings egg
and add
. We can replace e
with a
, g
with d
, and the resulting strings are add
and add
. Similarly, if we take and bar
, there is no consistent mapping that allows us to replace characters, so these strings are not isomorphic.
Complexity
Time complexity: O(n)
Space complexity: O(n)
Code
class Solution {
public:
bool isIsomorphic(string s, string t) {
unordered_map<char,char> mp, mp2;
for(int i=0; i<s.size(); i++){
if(mp[s[i]] && mp[s[i]]!=t[i]) return false;
if(mp2[t[i]] && mp2[t[i]]!=s[i]) return false;
mp[s[i]] = t[i];
mp2[t[i]] = s[i];
}
return true;
}
};