## Isomorphic Strings

07/16/2016 Hash Table

## Question

Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example:
Given "egg","add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

## Solution

Result: Accepted Time: 8 ms

Here should be some explanations.

class Solution {
public:
bool test(const string s,const string t)
{
const int len = s.size();
char m1={0},m2={0};
const char * ss = s.c_str();
const char * tt = t.c_str();
for(int i=0; i<len;i++)
{
if(!m1[ss[i]])
m1[ss[i]] = tt[i];
else if(m1[ss[i]] != tt[i])
return false;
if(!m2[tt[i]])
m2[tt[i]] = ss[i];
else if(m2[tt[i]] != ss[i])
return false;
}
return true;
}
bool isIsomorphic(string s, string t) {
return test(s,t) && test(t,s);
}
};


Complexity Analytics

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$