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

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:

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

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()