Pattern visualizer

Isomorphic Strings

The obvious half of this problem is easy: walk both strings together and remember what each letter of s turned into, so a letter that shows up again must turn into the same thing. That alone accepts pairs it should reject, because a renaming has to work in BOTH directions — if two different letters of s were allowed to become the same letter of t, you could never rename back, and the strings would not have the same shape. So a second rule is needed: a letter of t may be claimed only once. This trace fails on that second rule, not the first, which is where the usual one-map solution quietly gives the wrong answer. Animated on: s = "buttoning", t = "different" — can every letter of s be renamed to a letter of t consistently? Each cell shows the pairing one index demands..

One map, and the second rule everybody forgets

time O(n)space O(1)step 1 / 8

b→d

[0]

u→i

[1]

t→f

[2]

t→f

[3]

o→e

[4]

n→r

[5]

i→e

[6]

n→n

[7]

g→t

[8]

line 2

Each cell is the demand one index makes: "b→d" means index 0 needs 'b' to become 'd'. A pairing works only if it is a ONE-TO-ONE renaming, so two rules have to hold at every index: a letter of s must always become the SAME letter of t, and no two different letters of s may claim the same letter of t.

Pseudocode

1FUNCTION isIsomorphic(s, t)
2  map <- EMPTY MAP
3  FOR i <- 0 TO LENGTH(s) - 1
4    IF s[i] IN map
5      IF map[s[i]] != t[i]
6        RETURN false
7    ELSE
8      IF t[i] IN VALUES(map)
9        RETURN false
10      map[s[i]] <- t[i]
11  RETURN true

← / → step · space play · Home restart

Where to practice Strings

Practice Strings problems All Strings problems Back to roadmap