Isomorphic Strings

How it works

We can verify both mapping directions simultaneously in a single pass. By maintaining two hash maps, one for s -> t and one for t -> s, we check at each position that neither mapping is violated. If a character in s was previously mapped to a different character in t, or if a character in t was previously mapped to a different character in s, the strings aren't isomorphic.

Steps

1. Create two hash maps: mapST for s -> t and mapTS for t -> s.
2. Iterate through both strings simultaneously:
   • If s[i] already maps to something other than t[i], return false.
   • If t[i] already maps to something other than s[i], return false.
   • Otherwise, record both mappings.
3. If the loop completes without conflicts, return true.

Complexity

• Time complexity: O(n)
• Space complexity: O(m)

Where n is the length of the input string and m is the number of unique characters in the strings.

Things to watch for

Only Checking One Direction of Mapping

Checking only that each character in s maps to a unique character in t is insufficient. You must also verify the reverse: that each character in t maps to a unique character in s. For example, s = "ab" and t = "aa" would pass a one-way check but fails the bidirectional requirement since both 'a' and 'b' map to 'a'.

Assuming Same Character Sets

The two strings may contain completely different character sets. Do not assume that a character appearing in s must also appear in t, or vice versa. The mapping must be established dynamically as you iterate through both strings.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        mapST, mapTS = {}, {}

        for i in range(len(s)):
            c1, c2 = s[i], t[i]
            if ((c1 in mapST and mapST[c1] != c2) or
                (c2 in mapTS and mapTS[c2] != c1)):
                return False
            mapST[c1] = c2
            mapTS[c2] = c1

        return True

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> mapST, mapTS;

        for (int i = 0; i < s.size(); i++) {
            char c1 = s[i], c2 = t[i];

            if ((mapST.count(c1) && mapST[c1] != c2) ||
                (mapTS.count(c2) && mapTS[c2] != c1)) {
                return false;
            }

            mapST[c1] = c2;
            mapTS[c2] = c1;
        }

        return true;
    }
};