Sunday, September 10, 2017

205. Isomorphic Strings

https://leetcode.com/problems/isomorphic-strings/description/
Solution 0. Store the same index for the last appearance of s[i] and t[i] to two arrays. If the indices for s[i] and t[i] are different, they are not isomorphic.
    bool isIsomorphic(string s, string t) {
        if(s.size() != t.size()) return false;
        int mps[256] = {0}, mpt[256] = {0};
        for(int i=0; i<s.size(); i++) {
            if(mps[s[i]] != mpt[t[i]])
                return false;
            mps[s[i]] = i+1;
            mpt[t[i]] = i+1;
        }
        return true;
    }
Solution 1. Use array as map
    bool isIsomorphic(string s, string t) {
        if(s.size() != t.size()) return false;
        //vector<char> mps(256, 0), mpt(256, 0);
        char mps[256] = {0};
        char mpt[256] = {0};
        for(int i=0; i<s.size(); i++) {
            if(!mps[s[i]] && !mpt[t[i]]) {
                mps[s[i]] = t[i];
                mpt[t[i]] = s[i];
            }
            else if(mps[s[i]] != t[i] || mpt[t[i]] != s[i])
                return false;
        }
        return true;
    }
Solution 1.1 use map
    bool isIsomorphic(string s, string t) {
        if(s.size() != t.size()) return false;
        unordered_map<char,char> mp, mq;
        for(int i=0; i<s.size(); i++) {
            if(!mp.count(s[i]) && !mq.count(t[i])) {
                mp[s[i]] = t[i];
                mq[t[i]] = s[i];
            }
            else if(mp[s[i]] != t[i] || mq[t[i]] != s[i]) return false;
        }
        return true;
    }

No comments:

Post a Comment