LeetCode #205 Easy

Isomorphic Strings

Decide whether the characters of one string can be replaced consistently to produce another, preserving order.

stringhash-mapbijection

02

Intuition

💡

You will map s -> t and stop there, because that is what 'replace the characters' sounds like. It is half a check. Feed it s = 'badc', t = 'baba': b→b, a→a, then d→b and c→a are both brand new keys on the left, so a single forward map accepts them happily — even though b and d have now collapsed onto the same target letter, and so have a and c. Isomorphism is a BIJECTION, not just a function: distinct source characters must land on distinct targets, or the mapping cannot be undone. So carry the reverse map too, and at each index reject if fwd[s[i]] disagrees with t[i] OR rev[t[i]] disagrees with s[i]. Equivalently, keep one map plus a set of already-claimed targets. The invariant is that after every index the two maps are exact inverses of each other, which is precisely the property a one-to-one renaming has to satisfy.

03

Approach

1

Reject on length first

If the strings differ in length, no character-by-character correspondence exists at all, so return False before allocating anything. This also lets the main loop index both strings with a single counter without any bounds worry.

2

Maintain both directions

Keep fwd from characters of s to characters of t, and rev the other way. Walking the strings together, if s[i] is already in fwd its recorded image must equal t[i], and if t[i] is already in rev its recorded preimage must equal s[i]. The second condition is the one that catches the 'badc' / 'baba' collision, and it is why one map is not enough. When neither key exists, bind both at once so they stay inverses.

3

Fail fast, otherwise accept

Any single violated index is a complete disproof, so return False immediately rather than finishing the scan. If the loop completes, every character has a consistent partner in both directions and the strings are isomorphic. One pass over the input with maps bounded by the alphabet size gives O(n) time and O(1) space for a fixed alphabet.

04

Solution & live demo

python

▶1class Solution:
▶2    def isIsomorphic(self, s, t):
▶3        if len(s) != len(t):
▶4            return False
▶5        fwd, rev = {}, {}
▶6        for a, b in zip(s, t):
▶7            if a in fwd and fwd[a] != b:
▶8                return False
▶9            if b in rev and rev[b] != a:
▶10                return False
▶11            if a not in fwd:
▶12                fwd[a] = b
▶13                rev[b] = a
▶14            else:
▶15                pass
▶16        return True

05

Edge cases

Different lengths

Return False up front; no mapping can exist between sequences of different sizes.

A character mapping to itself, e.g. 'ab' -> 'ab'

Fine. Identity is a perfectly valid bijection; nothing requires the mapped letters to differ.

Two source characters wanting the same target, e.g. 'badc' -> 'baba'

The reverse map already holds that target under a different key, so the check fires and returns False — this is exactly the case a forward-only solution misses.

Empty strings

Lengths match, the loop body never runs, and True is returned; the empty mapping is trivially bijective.

06

Complexity

Time

O(n)

Space

O(1)

Both maps are bounded by the alphabet size rather than the input length, so the space is constant for a fixed character set.