Problem. Strings s and t are isomorphic if the characters of s can be replaced to get t, where:
- every occurrence of a character is replaced by the same character, and
- no two different characters map to the same character (a character may map to itself).
s = "egg", t = "add" → True (e → a, g → d)
s = "foo", t = "bar" → False (o would map to both a and r)
s = "badc", t = "baba" → False (b and d would both map to b)
ML context. "Same structure, different labels" appears when you compare clusterings (are two cluster assignments the same up to renaming the cluster ids?), align label schemes between datasets, or detect templated strings (log lines, product codes) that share a shape. The trick you learn here, a canonical form, is how you compare things up to renaming.
1. Step 1: Clarify
| Question | Answer | Why it matters |
|---|---|---|
| Same length? | Guaranteed here; otherwise False |
Free early exit |
| Character set? | Any ASCII (or Unicode) | Decides array versus dict |
| One-to-one in both directions? | Yes | The second condition needs a reverse check |
| Length? | Up to 5 × 10⁴ | Rules out anything quadratic |
2. Step 2: Brute force
Brute force A: check every pair of positions. The two conditions say: for every pair i, j,
s[i] == s[j] exactly when t[i] == t[j]. Check them all.
def isomorphic_pairs(s, t):
if len(s) != len(t):
return False
n = len(s)
for i in range(n):
for j in range(i + 1, n):
if (s[i] == s[j]) != (t[i] == t[j]): # equality pattern must match
return False
return True
assert isomorphic_pairs("egg", "add")
assert not isomorphic_pairs("foo", "bar")
assert not isomorphic_pairs("badc", "baba")
print("pair check works: O(n²) time, O(1) space")
O(n²): at n = 5 × 10⁴ that's about 1.25 × 10⁹ pair checks. Too slow, so optimise.
(Trying every possible renaming of the alphabet would be far worse: 26! renamings.)
3. Step 3: Optimise
Optimisation 1: build the mapping as you go (two hash maps)
The waste: the pair check rediscovers the same fact ("e goes with a") over and over. Instead, record the mapping the first time you see a character, and check every later occurrence against it.
One map s → t catches "one character with two images" (foo/bar). But it misses "two characters with one image"
(badc/baba: b → b and d → b are both fine for the forward map). So keep a second map t → s.
import random
def is_isomorphic(s, t):
if len(s) != len(t):
return False
s_to_t, t_to_s = {}, {}
for a, b in zip(s, t):
if s_to_t.get(a, b) != b or t_to_s.get(b, a) != a: # conflict in either direction
return False
s_to_t[a] = b
t_to_s[b] = a
return True
def brute(s, t):
return len(s) == len(t) and all((s[i] == s[j]) == (t[i] == t[j])
for i in range(len(s)) for j in range(i + 1, len(s)))
for s, t, want in [("egg", "add", True), ("foo", "bar", False), ("badc", "baba", False), ("paper", "title", True), ("", "", True)]:
assert is_isomorphic(s, t) == want
rng = random.Random(39)
for _ in range(2000):
n = rng.randint(0, 8)
s = "".join(rng.choice("abc") for _ in range(n))
t = "".join(rng.choice("xyz") for _ in range(n))
assert is_isomorphic(s, t) == brute(s, t)
print("two maps: O(n) time, O(alphabet) space, matches brute force on 2,000 cases")
- Time: O(n). Space: O(alphabet): at most one entry per distinct character, so O(1) for a fixed alphabet.
dict.get(a, b) != breads as: "ifaalready has an image, it must beb".
Quick check
Why does 'badc' vs 'baba' pass a single s → t map but fail isomorphism?
Show the answer
B. The forward map b→b, a→a, d→b, c→a has no conflicts, but b and d both map to b, which breaks one-to-one; only a reverse map t → s catches it — Injectivity needs checking in the other direction: two source characters must not share an image.
Optimisation 2: compare canonical forms
First principles: isomorphic strings have the same shape: the same pattern of "new character" versus "repeat of the k-th character". Encode each string by replacing every character with the index of its first occurrence. Two strings are isomorphic exactly when their codes are equal.
import random
def shape(s):
first = {}
return [first.setdefault(ch, len(first)) for ch in s] # new char → next id
def is_isomorphic_canonical(s, t):
return shape(s) == shape(t)
def two_maps(s, t):
if len(s) != len(t):
return False
st, ts = {}, {}
for a, b in zip(s, t):
if st.get(a, b) != b or ts.get(b, a) != a:
return False
st[a], ts[b] = b, a
return True
assert shape("paper") == [0, 1, 0, 2, 3] == shape("title")
assert shape("foo") != shape("bar")
rng = random.Random(40)
for _ in range(2000):
n = rng.randint(0, 8)
s = "".join(rng.choice("abc") for _ in range(n))
t = "".join(rng.choice("xyz") for _ in range(rng.choice([n, n + 1])))
assert is_isomorphic_canonical(s, t) == two_maps(s, t)
print("canonical shape codes agree with the two-map check")
Same O(n) time and O(n) space for the codes. Its real advantage shows up when you compare many strings (next section): a code is hashable, so it can be a dictionary key.
4. When the constraints change
| If the constraint becomes… | Best approach | Time | Space |
|---|---|---|---|
| Tiny strings | Pair check | O(n²) | O(1) |
| Classic | Two maps (or two 256-slot arrays for ASCII) | O(n) | O(alphabet) |
| Unicode | Two dicts | O(n) | O(distinct chars) |
| Group m strings by shape | Shape code as dict key | O(total length) | O(total length) |
| Strings arrive as a stream | Two maps, check each pair on arrival | O(1) per pair | O(alphabet) |
| Compare two clusterings | Same check on the label arrays | O(n) | O(clusters) |
Change A: group many strings by shape
Comparing every pair of m strings with the two-map check is O(m² · n). With a canonical code as a key, it's one pass.
from collections import defaultdict
def group_by_shape(words):
groups = defaultdict(list)
for w in words:
first = {}
key = tuple(first.setdefault(ch, len(first)) for ch in w)
groups[key].append(w)
return sorted(sorted(g) for g in groups.values())
assert group_by_shape(["egg", "add", "foo", "bar", "paper", "title", "abc"]) == [
["abc", "bar"], ["add", "egg", "foo"], ["paper", "title"]]
print("grouping by shape: one pass over all strings")
Change B: are two clusterings the same up to renaming?
Two runs of k-means give label arrays like [0, 0, 1, 2, 2] and [2, 2, 0, 1, 1]. They describe the same
clustering exactly when the label arrays are "isomorphic". Same function, different data.
def same_clustering(a, b):
first_a, first_b = {}, {}
return [first_a.setdefault(x, len(first_a)) for x in a] == [first_b.setdefault(x, len(first_b)) for x in b]
assert same_clustering([0, 0, 1, 2, 2], [2, 2, 0, 1, 1])
assert not same_clustering([0, 0, 1, 1], [0, 1, 1, 1])
print("two clusterings compared up to renaming the cluster ids")
(When the clusterings are only mostly the same, you'd use a similarity score like the adjusted Rand index; this exact check is its strict special case.)
Quick check
You must group 10⁵ log lines by 'shape' (same pattern of repeated tokens). What's efficient?
Show the answer
A. Compute each line's first-occurrence code once and use it as a dictionary key: one pass — A canonical form turns pairwise comparison into hashing.
5. Saying it out loud
"Checking every pair of positions is O(n²). Instead I'll build the mapping as I go with two maps, s to t and t to s, so I catch both a character with two images and two characters sharing one: O(n) time, space bounded by the alphabet. Equivalently, I can encode each string by first-occurrence indices; equal codes mean isomorphic, and the code works as a dict key to group many strings."
Check yourself
- What condition on pairs of positions defines isomorphism?
- Which failure does the forward map catch, and which needs the reverse map?
- Why is the space O(1) for a fixed alphabet?
- What is the first-occurrence code of "paper"?
- How do you group many strings by shape efficiently?
- How does this check apply to comparing two clusterings?
Answers
- For all i, j:
s[i] == s[j]exactly whent[i] == t[j]. - Forward: one character mapped to two images (foo/bar). Reverse: two characters mapped to the same image (badc/baba).
- Each map holds at most one entry per distinct character, bounded by the alphabet size.
- [0, 1, 0, 2, 3].
- Use each string's code (as a tuple) as a dictionary key: one pass.
- Two label arrays describe the same clustering exactly when they're isomorphic (equal first-occurrence codes).