Can each letter of s turn into one letter of t, with no two sharing? A two-way codebook settles it in a single pass.
▼The problem
LeetCode 205 (Easy). Given two strings s and t of the same length, return true if they are isomorphic: the characters of s can be replaced to get t, every occurrence of a character is replaced by the same character, and no two characters map to the same character (a character may map to itself).
Examples (LeetCode's three, plus one that fails only in reverse): ("egg", "add") → true (e → a, g → d; walked through in scene 6), ("foo", "bar") → false (o would need to be both a and r), ("paper", "title") → true (p → t, a → i, e → l, r → e) and ("badc", "baba") → false: every letter of s does give one letter of t (b → b, a → a, d → b, c → a), so a forward map alone accepts it, but b and d would both become b; the reverse map catches it at position 2 (scene 6).
The solution
def isIsomorphic(s, t):
s2t, t2s = {}, {}
for a, b in zip(s, t):
if s2t.get(a, b) != b or t2s.get(b, a) != a:
return False
s2t[a] = b
t2s[b] = a
return TrueTranscript
Isomorphic Strings. Given two strings, s and t, can you swap each letter of s for one letter and get t? Each letter always becomes the same letter, and no two letters share one.
Egg and add works: E becomes A, G becomes D. True. Foo and bar fails: O would need to be both A and R. False. Paper and title works too. But B A D C against B A B A fails: B and D would both become B.
The slow way checks every pair of positions: letters of s match exactly when the letters below them match. That's n squared pairs.
Better: one pass with a two-way codebook. One column maps s to t, the other maps t back to s. If the s letter is already coded, it must give this t letter, and the t letter must point back. Otherwise, write both.
In code: two dictionaries, one loop. If either lookup disagrees, return false. Otherwise record both, and finish true.
Decode egg into add. E is new: write E to A, A back to E. G to D, D back to G. The second G: the book says D, and D points back to G. True. Now B A D C. B and A code to themselves. D wants B, but B already points back to B. A forward map alone would miss that. False.
One pass, so time is order n. The books hold a fixed alphabet, so space is constant.
Map forward, map back, stop at the first clash. That's Isomorphic Strings.