# LeetCode 205: Isomorphic Strings

## Problem Restatement

We are given two strings:

```python
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:

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

## Examples

Example 1:

```python
s = "egg"
t = "add"
```

Mapping:

```text
e -> a
g -> d
```

The structure matches.

Answer:

```python
True
```

Example 2:

```python
s = "foo"
t = "bar"
```

Try mapping:

```text
f -> b
o -> a
```

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

That breaks consistency.

Answer:

```python
False
```

Example 3:

```python
s = "paper"
t = "title"
```

Mapping:

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

The repeated characters also match correctly.

Answer:

```python
True
```

## Understanding the Structure

The problem is really about patterns.

Example:

```python
s = "egg"
```

Pattern:

```text
first char
second char
second char
```

Now:

```python
t = "add"
```

Pattern:

```text
first char
second char
second char
```

The structures are identical.

Now compare:

```python
s = "foo"
t = "bar"
```

Patterns:

```text
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:

```python
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:

```text
s character -> t character
```

Example:

```python
s = "ab"
t = "cc"
```

We would store:

```text
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:

```python
s = "paper"
t = "title"
```

Initial maps:

```python
s_to_t = {}
t_to_s = {}
```

First pair:

```text
p -> t
```

Store:

```text
s_to_t[p] = t
t_to_s[t] = p
```

Next pair:

```text
a -> i
```

Store it.

Later:

```text
p -> t
```

This matches the previous mapping, so continue.

Eventually every pair stays consistent.

Return:

```python
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

```python
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:

```python
s_to_t = {}
t_to_s = {}
```

Process both strings together:

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

If `a` already has a mapping:

```python
if a in s_to_t:
```

check consistency:

```python
if s_to_t[a] != b:
    return False
```

Otherwise create the mapping:

```python
s_to_t[a] = b
```

Then repeat the same logic in reverse using `t_to_s`.

If no contradiction appears, return:

```python
True
```

## Alternative Pattern-Based Solution

Another elegant solution compares structural patterns.

Example:

```python
egg
```

Pattern indices:

```text
0 1 1
```

Example:

```python
add
```

Pattern indices:

```text
0 1 1
```

The patterns match.

Implementation:

```python
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

```python
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 |