Isomorphic Strings (LeetCode 205)

The problem

You get two strings s and t of the same length. They are isomorphic if you can replace every character of s with some character so that s becomes t, under two rules: every copy of a character must map to the same character, and no two different characters may map to the same one. A character may map to itself.

Input:  s = "egg", t = "add"
Output: True

Input:  s = "foo", t = "bar"
Output: False

e -> a and g -> d turns "egg" into "add". In "foo", both os would have to become a and r, which is impossible.

How to think about it

Start with brute force. You could try every possible renaming of the characters of s, but that is factorial in the alphabet size. Instead, notice that the renaming is forced: the first time you see s[i], it must map to t[i]. So there’s nothing to search, only something to check.

The first rule needs one map. Walk the strings together. Keep m1 from characters of s to characters of t. If s[i] already has a mapping, it must equal t[i]; otherwise record it. That catches "foo" / "bar".

The key insight: the second rule needs a second map. One map alone accepts "badc" / "baba": b -> b, a -> a, d -> b, c -> a. Each character of s is consistent, but b and d both map to b. To catch that, keep m2 from t back to s and apply the same check. A one-to-one mapping must hold in both directions, so you check both on every pair.

Which pattern is this? Hash map consistency checking. The tell is “same pattern / structure” between two sequences (see also Word Pattern, LeetCode 290).

Approach

1. Create two empty maps: m1 (s to t) and m2 (t to s).
2. For each pair (a, b) from zip(s, t):
   • if a is already mapped to something other than b, return False;
   • if b is already mapped to something other than a, return False;
   • otherwise record m1[a] = b and m2[b] = a.
3. If every pair passes, return True.

Solution

def is_isomorphic(s, t):
    m1, m2 = {}, {}                                       # s->t and t->s
    for a, b in zip(s, t):
        if m1.get(a, b) != b or m2.get(b, a) != a: return False   # conflict either way
        m1[a] = b; m2[b] = a
    return True
# is_isomorphic("egg", "add") -> True ; is_isomorphic("foo", "bar") -> False

m1.get(a, b) returns b when a is not yet mapped, so a new character always passes the check.

Dry run

On s = "foo", t = "bar":

On "badc" / "baba", the third pair (d, b) passes m1 (since d is new) but fails m2, because m2[b] is already b, not d. That’s exactly the case one map would miss.

Complexity

• Time: O(n). One pass with O(1) dictionary operations.
• Space: O(1). Each map holds at most one entry per distinct character (at most 256 for ASCII).

Edge cases and pitfalls

• One map only: the most common bug. It accepts "badc" / "baba", which is wrong.
• Different lengths: zip silently stops at the shorter string. The problem guarantees equal lengths; add a length check if it doesn’t.
• Empty strings: trivially isomorphic, returns True.
• Self-mapping is allowed: "paper" / "title" is True, and "ab" / "ab" is too.
• Alternative: compare the “first-seen index” sequence of each string, for example [s.index(c) for c in s]. It’s correct but O(n²) with index; build the sequence with a dictionary to keep it O(n).

Related problems

• Group Anagrams (LeetCode 49): another problem about a canonical “shape” of a string.
• Valid Anagram (LeetCode 242): character-level hash maps across two strings.
• Two Sum (LeetCode 1): the basic “store as you scan, check on arrival” loop.