Module 02 · Hash Maps, Sets, and Frequency State

017. Isomorphic Strings

Bridge · Download this solution · All solutions and shared helpers

Problem

Return whether two strings admit a consistent one-to-one character substitution from a to b. Each source character maps to one target character, and two different source characters cannot share a target. Lengths must match. A character may map to itself.

Examples

Example 1

isomorphic("egg", "add")
=> True

Repeated g consistently maps to d.

Example 2

isomorphic("ab", "xx")
=> False

Two source characters cannot map to one target.

Example 3

isomorphic("", "")
=> True

The empty mapping is valid.

Reveal the worked solution and reasoning

Why this mechanism works

A forward map enforces consistency but not injectivity: it would allow both a and b to map to x. A reverse map enforces that the target character has only one source. Check both directions before extending the mapping.

State and boundaries

forward and reverse encode mutually consistent character pairs established by earlier positions.

Protocol

Reject unequal lengths.
For each aligned character pair check any existing forward mapping.
Check the reverse mapping too.
Record the pair in both dictionaries.
Accept when all pairs pass.

Visualization

egg -> add
e <-> a
g <-> d
second g reuses g <-> d

Python implementation

def isomorphic(a, b):
    if len(a) != len(b):
        return False
    forward, reverse = {}, {}
    for x, y in zip(a, b):
        if x in forward and forward[x] != y:
            return False
        if y in reverse and reverse[y] != x:
            return False
        forward[x], reverse[y] = y, x
    return True

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

isomorphic("egg", "add")

L2 isomorphic: if len(a) != len(b):
a='egg'; b='add'

L4 isomorphic: forward, reverse = {}, {}
a='egg'; b='add'; forward={}; reverse={}

L5 isomorphic: for x, y in zip(a, b):
a='egg'; b='add'; forward={}; reverse={}; x='e'; y='a'

L10 isomorphic: forward[x], reverse[y] = y, x
a='egg'; b='add'; forward={'e':'a'}; reverse={'a':'e'}; x='e'; y='a'

L5 isomorphic: for x, y in zip(a, b):
a='egg'; b='add'; forward={'e':'a'}; reverse={'a':'e'}; x='g'; y='d'

L10 isomorphic: forward[x], reverse[y] = y, x
a='egg'; b='add'; forward={'e':'a', 'g':'d'}; reverse={'a':'e', 'd':'g'}; x='g'; y='d'

Result: True. Repeated g consistently maps to d.

isomorphic("ab", "xx")

L2 isomorphic: if len(a) != len(b):
a='ab'; b='xx'

L4 isomorphic: forward, reverse = {}, {}
a='ab'; b='xx'; forward={}; reverse={}

L5 isomorphic: for x, y in zip(a, b):
a='ab'; b='xx'; forward={}; reverse={}; x='a'; y='x'

L10 isomorphic: forward[x], reverse[y] = y, x
a='ab'; b='xx'; forward={'a':'x'}; reverse={'x':'a'}; x='a'; y='x'

L5 isomorphic: for x, y in zip(a, b):
a='ab'; b='xx'; forward={'a':'x'}; reverse={'x':'a'}; x='b'; y='x'

Result: False. Two source characters cannot map to one target.

Why the solution is correct

Each accepted pair preserves functional consistency in both directions. The resulting forward relation is therefore one-to-one and explains every aligned position. Any rejected pair contradicts a required earlier mapping, so no valid substitution could exist.

Time and space

O(n) expected time and O(u+v) space for distinct characters in the strings.

Common mistakes

A forward-only map accepts ab -> xx incorrectly. Frequency equality is neither the intended order constraint nor a substitute for checking aligned positions.

Reasoning card

State: forward and reverse encode mutually consistent character pairs established by earlier positions.

Invariant: Every established mapping remains consistent and bijective.

Decision to rehearse: Maintain both forward and reverse mappings.

Finish: Accept when all pairs pass

Transfer exercise

Use the same bijection idea to match a word pattern such as abba against a sentence.