Isomorphic Strings

Easy#205two maps

You get two strings of the same length, s and t. Find out whether the letters of s can be replaced to get t: one letter always turns into the same letter, and two different letters never turn into the same one. Our example: "stone" and "ladle" — no: both s and n would have to become l.

205 Isomorphic StringsWalkthrough · 1×

Example: s = "stone", t = "ladle". Under them are both maps: what each letter of s turns into, and where each letter of t came from.

st0s1t2o3n4eladletoTs → t—toSt → s—
not reached yetcurrent paircheckedthe clash

toT will say what each letter of s turns into

01/22
restart · back · play · step
Speed
1function isIsomorphic(s, t):
2 toT = empty map
3 toS = empty map
4 for i from 0 to len(s) - 1:
5 a = s[i]; b = t[i]
6 if a in toT and toT[a] != b:
7 return false
8 if b in toS and toS[b] != a:
9 return false
10 toT[a] = b; toS[b] = a
11 return true
state
toT
{}
toS
–
i
–
a
–
b
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The replacement is a rule letter → letter. A letter of s must always turn into the same letter of t: toT remembers what each one turned into.
  2. Two different letters of s must not turn into the same letter of t: toS remembers where each letter of t came from. With toT alone, "stone" → "ladle" would pass, since n is new there.
  3. One clash in either map means false. If the strings end with no clash, the rule works both ways: true.

Complexity

Time O(n): one pass, map lookups are O(1). Memory O(1): each map has at most one entry per letter of the alphabet, however long the strings.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.