Run it: Isomorphic strings in code
The two-map version and the single-map version run side by side, on the input that separates them, plus the canonical-form other reaching the same verdicts.
Two maps, not one
O(n) time, O(k) space where k is the alphabet size.
Checking only forward accepts "badc" / "baba": b→b, a→a, d→b... which conflicts, so that given pair is caught. But "ab" / "aa" is not — a→a and b→a are both steady forwards. And they map two characters to one.
The second map is what enforces injectivity, and stating why it is needed. With a counterexample. Is the substance of a good answer.
The pattern-normalisation other
An elegant one-liner: two strings are isomorphic just when their instance patterns match.
"egg" gives [0, 1, 1] and "add" gives [0, 1, 1]. Equal, so isomorphic. "foo" gives [0, 1, 1] and "bar" gives [0, 1, 2] — different.
This by itself handles both ways, because the pattern is a canonical form. The catch is that x.index(ch) is O(n). This makes the whole thing O(n²). Fixing it with a dictionary restores O(n):
Worth offering as the canonical-form view after the two-map version, because it is the same idea that solves the "group anagrams" family. Normalise, then compare.
What isomorphic means here
There must be a one-to-one correspondence between the characters. Replacing each character of the first string according to a fixed rule gives the second. And no two characters map to the same target. "Same shape, different letters".
A length check is a free first rejection, and the empty string is isomorphic to itself. The canonical-form view makes the whole thing one check: encode each string as the first-instance index of each character, so "paper" turns [0, 1, 0, 2, 3] and "title" turns [0, 1, 0, 2, 3]. The same, so isomorphic — while "foo" gives [0, 1, 1] and "bar" gives [0, 1, 2], which differ at the third spot. Because the pattern is canonical it checks both ways at once, which is just what the two-map version needs a second map to do.
Why one map is not enough
Track only a → b and "badc" against "baba" passes: b→b, a→a, d→b, c→a. Each forward rule is steady, and two distinct characters have collapsed onto one target.
The reverse map catches it: b is now claimed by b. So d→b is rejected. Both ways are needed because a bijection is a constraint in both ways.
Normalise each string to the pattern of first appearances. "paper" and "title" both turn [0,1,2,0,3]. And compare the patterns. One pass each, no paired bookkeeping, and it extends naturally to comparing many strings at once by using the pattern as a dictionary key.
That is the same "canonicalise, then compare" idea as grouping anagrams. This is worth pointing out.
Edge cases
| Case | Result |
|---|
| Different lengths | False — check first, it is O(1) |
| Both empty | True |
| Single characters | True, whatever they are |
| Same string | True — the identity mapping |
"aa" / "ab" | False — a cannot map to two characters |
"ab" / "aa" | False — needs the backward map |
| All distinct in both | True, if lengths match |
| Unicode | Works — dictionaries handle any hashable character |
The two "ab"/"aa" rows are the pair to test: one way catches the first. And only the second map catches the second. Mentioning both shows that the bijection requirement is understood rather than copied.
The tied problems
Word pattern. The same problem with words instead of characters. Does "dog cat cat dog" match the pattern "abba"? The same structure over s.split().
Group isomorphic strings. Use the normalised pattern as a dictionary key, just as sorted characters group anagrams. The canonical-form technique again.
Isomorphic graphs. Superficially tied and vastly harder — graph isomorphism has no known polynomial algorithm. Worth knowing the distinction if it comes up, because the name invites confusion.
Find and replace with a steady mapping. The real version: applying a cipher or a tokenisation always.
| Problem | Canonical form |
|---|
| Isomorphic strings | First-occurrence index pattern |
| Anagrams | Sorted characters, or a count tuple |
| Rotations | Smallest rotation, or b in a + a |
| Case-insensitive equality | Casefolded string |
That table is the transferable lesson: when a problem asks whether two things are the same under some transformation, compute a canonical form and compare. It turns an equivalence test into a hash lookup. This is what makes grouping doable.