How to Check if Two Strings are Isomorphic?

Two strings are isomorphic if the characters in one string can be replaced to get another one. No two characters may map to the same character. A character can map to itself. Also, the order of occurrences of all characters must be preserved when mapping one string to another.

For example, “egg” and “add” are isomorphic but “foo” and “bar” are not.

Two strings cannot be isomorphic if they have different lengths. When iterating the characters one by one, we use a hash table to record the mapping the character from one string to another at the meantime another hash table or hash set i.e. unordered_set to check if that target character has been mapped previously.

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size()) return false;
        unordered_map<char, char> data;
        unordered_set<char> data2;
        for (int i = 0; i < s.size(); ++ i) {
            if (data.find(s[i]) == data.end()) {
                if (data2.count(t[i])) { // no two characters may map to the same character.
                    return false;
                }
                data[s[i]] = t[i];
                data2.insert(t[i]);
            }
            if (data[s[i]] != t[i]) return false;
        }
        return true;
    }
};

The above algorithms runs time complexity O(N) and space complexity O(N) – one hash table and one hash set.

–EOF (The Ultimate Computing & Technology Blog) —