6. Isomorphic Strings

Two strings are isomorphic if the characters in s can be replaced to get t.

Example 1:
Input: s = "egg", t = "add"
Output: true

Example 2:
Input: s = "foo", t = "bar"
Output: false

Example 3:
Input: s = "paper", t = "title"
Output: true

Solution: (hashmaps)

Approach: Two string must be of same length. Map each character of string swith a character of string t. And the character of the string t should not be mapped with any other char of string s.

class Solution
{
public:
    bool isIsomorphic(string s, string t)
    {

        unordered_map<char, char> m;
        for (int i = 0; i < s.length(); i++)
        {

            if (m.find(s[i]) == m.end())
            {
                for (auto itr = m.begin(); itr != m.end(); itr++)
                {
                    if (itr->second == t[i])
                    {
                        return false;
                    }
                }
                m.insert({s[i], t[i]});
            }
            else
            {

                char ch = m[s[i]];
                if (ch != t[i])
                {
                    return false;
                }
            }
        }

        return true;
    }
};

But this takes an Time Complexity: O(n*n) as we need to search if a char is mapped earlier or not.

Efficient Approach: (using hashset and hashmap)

class Solution
{
public:
    bool isIsomorphic(string s, string t)
    {

        unordered_map<char, char> m;
        unordered_set<char> v;
        for (int i = 0; i < s.length(); i++)
        {

            if (m.find(s[i]) == m.end() && v.find(t[i]) == v.end())
            {
                m.insert({s[i], t[i]});
                v.insert(t[i]);
            }
            else if(m.find(s[i]) == m.end() && v.find(t[i]) != v.end()){
                return false;
            }
            else
            {

                char ch = m[s[i]];
                if (ch != t[i])
                {
                    return false;
                }
            }
        }

        return true;
    }
};

Time Complexity: O(n)