205 Isomorphic Strings

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.

Solution

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int ns = s.size(), nt = t.size();
        if ( ns != nt ) return false;
        unordered_map<char, vector<int>> map_s, map_t;
        for ( int i = 0; i <= ns-1; i++ ) {
            char cs = s[i], ct = t[i];
            if ( map_s.find(cs) == map_s.end() and map_t.find(ct) != map_t.end() ) return false;
            if ( map_s.find(cs) != map_s.end() and map_t.find(ct) == map_t.end() ) return false;
            if ( map_s.find(cs) == map_s.end() ) { vector<int> tmp(1, i); map_s[cs] = tmp; }
            if ( map_t.find(ct) == map_t.end() ) { vector<int> tmp(1, i); map_t[ct] = tmp; }
            if ( map_s.find(cs) != map_s.end() and map_t.find(ct) != map_t.end() ) {
                vector<int> vs = map_s[cs], vt = map_t[ct];
                if ( vs.size() != vt.size() ) return false;
                if ( vs[vs.size()-1] != vt[vt.size()-1] ) return false;
                map_s[cs].push_back(i);
                map_t[ct].push_back(i);
            }
        }
        return true;
    }
};

Use map_s to map from s to t and map_t to map from t to s

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int ns = s.size(), nt = t.size();
        if ( ns != nt ) return false;
        unordered_map<char, char> map_s, map_t;
        for ( int i = 0; i <= ns-1; i++ ) {
            if ( map_s.find(s[i]) == map_s.end() ) map_s[s[i]] = t[i];
            else {
                if ( map_s[s[i]] != t[i] ) return false;
            }
            if ( map_t.find(t[i]) == map_t.end() ) map_t[t[i]] = s[i];
            else {
                if ( map_t[t[i]] != s[i] ) return false;
            }
        }
        return true;
    }
};

Use vector instead of map to gain efficiency
Note the trick to use int(char x) as index for a vector(array).

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int ns = s.size(), nt = t.size();
        if ( ns != nt ) return false;
        int MAXCHAR = 256;
        vector<char> vs(MAXCHAR, ' '), vt(MAXCHAR, ' ');
        for ( int i = 0; i <= ns-1; i++ ) {
            if ( vs[s[i]] == ' ' ) vs[s[i]] = t[i];
            else {
                if ( vs[s[i]] != t[i] ) return false;
            }
            if ( vt[t[i]] == ' ' ) vt[t[i]] = s[i];
            else {
                if ( vt[t[i]] != s[i] ) return false;
            }
        }
        return true;
    }
};