LeetCode 205: Isomorphic Strings

Problem Restatement

We are given two strings:

s
t

We need to determine whether the two strings are isomorphic.

Two strings are isomorphic when characters from s can be replaced to form t while preserving structure.

Rules:

1. Every character in s must map to exactly one character in t.
2. Different characters in s cannot map to the same character in t.
3. A character may map to itself.

The official statement says: given two strings s and t, determine if they are isomorphic. Two strings are isomorphic if the characters in s can be replaced to get t, with all occurrences of a character replaced by another character while preserving order. No two characters may map to the same character, but a character may map to itself.

Input and Output

Item	Meaning
Input	Two strings s and t
Output	True if the strings are isomorphic, otherwise False
Constraint	Mapping must be one-to-one
Order	Character order must stay consistent

Example function shape:

def isIsomorphic(s: str, t: str) -> bool:
    ...

Examples

Example 1:

s = "egg"
t = "add"

Mapping:

e -> a
g -> d

The structure matches.

Answer:

True

Example 2:

s = "foo"
t = "bar"

Try mapping:

f -> b
o -> a

But the second o would also need to map to r.

That breaks consistency.

Answer:

False

Example 3:

s = "paper"
t = "title"

Mapping:

p -> t
a -> i
e -> l
r -> e

The repeated characters also match correctly.

Answer:

True

Understanding the Structure

The problem is really about patterns.

Example:

s = "egg"

Pattern:

first char
second char
second char

Now:

t = "add"

Pattern:

first char
second char
second char

The structures are identical.

Now compare:

s = "foo"
t = "bar"

Patterns:

foo -> first second second
bar -> first second third

The patterns differ.

So the strings are not isomorphic.

First Thought

We can scan both strings at the same time.

For each pair of characters:

s[i]
t[i]

we record the mapping.

If we ever see a contradiction, return False.

Otherwise continue.

Why One Dictionary Is Not Enough

Suppose we only store:

s character -> t character

Example:

s = "ab"
t = "cc"

We would store:

a -> c
b -> c

This incorrectly looks valid.

But two different characters from s cannot map to the same character in t.

So we also need the reverse check.

Key Insight

We need a one-to-one mapping.

That means:

Direction	Meaning
s -> t	Same character in s always maps consistently
t -> s	Different characters in s cannot share the same target

So we maintain two hash maps.

Algorithm

1. Create two dictionaries:
   • s_to_t
   • t_to_s
2. Scan both strings together.
3. For each pair (a, b):
   • If a already maps to another character, return False.
   • If b already maps to another character, return False.
   • Otherwise store the mapping.
4. If the scan finishes successfully, return True.

Walkthrough

Use:

s = "paper"
t = "title"

Initial maps:

s_to_t = {}
t_to_s = {}

First pair:

p -> t

Store:

s_to_t[p] = t
t_to_s[t] = p

Next pair:

a -> i

Store it.

Later:

p -> t

This matches the previous mapping, so continue.

Eventually every pair stays consistent.

Return:

True

Correctness

The algorithm processes corresponding characters from s and t one position at a time.

For every pair (a, b):

• s_to_t guarantees that each character from s always maps to the same character in t.
• t_to_s guarantees that no two characters from s map to the same character in t.

If either condition is violated, the strings cannot be isomorphic, so returning False is correct.

If the scan finishes without contradiction, then:

1. Every character in s maps consistently.
2. The mapping is one-to-one.
3. Character order is preserved because the strings are scanned position by position.

Therefore the transformation from s to t is valid, so the strings are isomorphic.

Complexity

Metric	Value	Why
Time	O(n)	Each character pair is processed once
Space	O(n)	Dictionaries may store up to all unique characters

Implementation

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s_to_t = {}
        t_to_s = {}

        for a, b in zip(s, t):
            if a in s_to_t:
                if s_to_t[a] != b:
                    return False
            else:
                s_to_t[a] = b

            if b in t_to_s:
                if t_to_s[b] != a:
                    return False
            else:
                t_to_s[b] = a

        return True

Code Explanation

Create two dictionaries:

s_to_t = {}
t_to_s = {}

Process both strings together:

for a, b in zip(s, t):

If a already has a mapping:

if a in s_to_t:

check consistency:

if s_to_t[a] != b:
    return False

Otherwise create the mapping:

s_to_t[a] = b

Then repeat the same logic in reverse using t_to_s.

If no contradiction appears, return:

True

Alternative Pattern-Based Solution

Another elegant solution compares structural patterns.

Example:

egg

Pattern indices:

0 1 1

Example:

add

Pattern indices:

0 1 1

The patterns match.

Implementation:

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        return self.pattern(s) == self.pattern(t)

    def pattern(self, text: str):
        seen = {}
        result = []

        for i, ch in enumerate(text):
            if ch not in seen:
                seen[ch] = len(seen)

            result.append(seen[ch])

        return result

This converts each string into a normalized structural representation.

Testing

def run_tests():
    s = Solution()

    assert s.isIsomorphic("egg", "add") is True
    assert s.isIsomorphic("foo", "bar") is False
    assert s.isIsomorphic("paper", "title") is True
    assert s.isIsomorphic("ab", "aa") is False
    assert s.isIsomorphic("badc", "baba") is False
    assert s.isIsomorphic("a", "a") is True

    print("all tests passed")

run_tests()

Test	Why
"egg", "add"	Standard valid mapping
"foo", "bar"	Repeated character mismatch
"paper", "title"	Larger valid structure
"ab", "aa"	Two characters mapping to one
"badc", "baba"	Reverse mapping conflict
"a", "a"	Smallest valid case