Isomorphic Strings

Problem: 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.

Example:

Input: s = "eef", t = "ggh"
Output: true

Input: s = "ab", t = "aa"
Output: false

Approach: We can use hash to maintain which character of s is mapped to which character to t and if we see that a same character of s is not getting mapped to same character of t, we can return false but this approach will fail in case of our second example (s = "ab", t = "aa"). Here is what will happen -

1. s[0] = 'a', t[0] = 'a',  'a' does not exist in hash so we will do hash['a'] = 'a'.
2. s[1] = 'b', t[1] = 'a' again 'b' does not exist in has so we will add 'b' in to hash; hash['b'] = 'a'.

So ultimately we will return true which is not correct as a and b both can't be replaced by a that mean we need reverse mapping too. Either we can maintain similar hash or we can just maintain a hashset which will tell us whether the current character of t is used before or not. That's all about the solution.

Implementation in C#:

        public bool IsIsomorphic(string s, string t)

        {

            if (s.Length != t.Length)

            {

                return false;

            }

            Dictionary<char, char> hash = new Dictionary<char, char>();

            HashSet<char> used = new HashSet<char>();

            for (int i = 0; i < s.Length; ++i)

            {

                if (hash.ContainsKey(s[i]))

                {

                    if (hash[s[i]] != t[i])

                    {

                        return false;

                    }

                }

                else

                {

                    if (used.Contains(t[i]))

                    {

                        return false;

                    }

                    hash.Add(s[i], t[i]);

                    used.Add(t[i]);

                }

            }

            return true;

        }

Complexity: O(n)