# LeetCode 290: Word Pattern

## Problem Restatement

We are given two strings:

```python
pattern
s
```

`pattern` contains letters.

`s` contains words separated by spaces.

We need to check whether `s` follows the same pattern.

“Follows the same pattern” means there must be a bijection between pattern letters and words. In other words, each pattern letter maps to exactly one word, and each word maps back to exactly one pattern letter.

For example:

```python
pattern = "abba"
s = "dog cat cat dog"
```

This is valid because:

| Pattern Letter | Word |
|---|---|
| `a` | `"dog"` |
| `b` | `"cat"` |

The mapping is consistent in both directions.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A pattern string `pattern` and a space-separated string `s` |
| Output | `True` if `s` follows `pattern`, otherwise `False` |
| Required relation | Bijection between letters and words |

Function shape:

```python
class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        ...
```

## Examples

For:

```python
pattern = "abba"
s = "dog cat cat dog"
```

The result is:

```python
True
```

because `a` always maps to `"dog"` and `b` always maps to `"cat"`.

For:

```python
pattern = "abba"
s = "dog cat cat fish"
```

The result is:

```python
False
```

because `a` maps to `"dog"` at first, but the last `a` would need to map to `"fish"`.

For:

```python
pattern = "aaaa"
s = "dog cat cat dog"
```

The result is:

```python
False
```

because one pattern letter cannot map to multiple different words.

For:

```python
pattern = "abba"
s = "dog dog dog dog"
```

The result is:

```python
False
```

because two different pattern letters, `a` and `b`, cannot both map to `"dog"`.

## First Thought: One Hash Map

A first idea is to map each pattern letter to a word.

For example:

```python
a -> dog
b -> cat
```

Then, while scanning the input, if we see the same pattern letter again, it must map to the same word.

Code idea:

```python
char_to_word = {}
```

This catches cases like:

```python
pattern = "abba"
s = "dog cat cat fish"
```

because `a` first maps to `"dog"`, then later tries to map to `"fish"`.

But one map alone misses the reverse conflict.

For example:

```python
pattern = "abba"
s = "dog dog dog dog"
```

A map from character to word can store:

```python
a -> dog
b -> dog
```

But this is invalid because different pattern letters cannot map to the same word.

So we need to check both directions.

## Key Insight

A bijection needs two constraints:

| Direction | Constraint |
|---|---|
| Pattern letter to word | One letter always maps to the same word |
| Word to pattern letter | One word always maps to the same letter |

So we keep two hash maps:

```python
char_to_word = {}
word_to_char = {}
```

For each pair `(char, word)`:

1. If `char` already maps to another word, return `False`.
2. If `word` already maps to another char, return `False`.
3. Otherwise, record both mappings.

## Algorithm

Split `s` into words:

```python
words = s.split()
```

If the number of words differs from the number of pattern letters, return `False`.

Then scan both lists together.

For each pair:

```python
char = pattern[i]
word = words[i]
```

Check the forward map:

```python
if char in char_to_word and char_to_word[char] != word:
    return False
```

Check the reverse map:

```python
if word in word_to_char and word_to_char[word] != char:
    return False
```

If both checks pass, store:

```python
char_to_word[char] = word
word_to_char[word] = char
```

If the loop finishes, return `True`.

## Correctness

The algorithm rejects exactly the cases that violate the required bijection.

If a pattern letter appears again with a different word, the forward map detects the conflict. This prevents one letter from mapping to multiple words.

If a word appears again with a different pattern letter, the reverse map detects the conflict. This prevents multiple letters from mapping to the same word.

If neither conflict occurs for every pair, then every pattern letter has one consistent word, and every word has one consistent pattern letter.

The length check ensures that every pattern letter is paired with exactly one word and no extra word remains unmatched.

Therefore the algorithm returns `True` exactly when `s` follows `pattern`.

## Complexity

Let:

```python
n = len(pattern)
m = len(s)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n + m)` | Splitting `s` scans the string, then we scan the pattern |
| Space | `O(n + m)` | The words list and hash maps store input-derived strings |

## Implementation

```python
class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()

        if len(pattern) != len(words):
            return False

        char_to_word = {}
        word_to_char = {}

        for char, word in zip(pattern, words):
            if char in char_to_word and char_to_word[char] != word:
                return False

            if word in word_to_char and word_to_char[word] != char:
                return False

            char_to_word[char] = word
            word_to_char[word] = char

        return True
```

## Code Explanation

We first split the sentence into words:

```python
words = s.split()
```

Then we check whether the counts match:

```python
if len(pattern) != len(words):
    return False
```

A full match requires one word for every pattern letter.

The first map stores character-to-word relationships:

```python
char_to_word = {}
```

The second map stores word-to-character relationships:

```python
word_to_char = {}
```

For each pair:

```python
for char, word in zip(pattern, words):
```

we check whether either direction conflicts with an earlier mapping.

If a conflict exists, the pattern fails immediately.

If no conflict exists, we record both mappings:

```python
char_to_word[char] = word
word_to_char[word] = char
```

After all pairs pass, the string follows the pattern:

```python
return True
```

## Testing

```python
def test_word_pattern():
    s = Solution()

    assert s.wordPattern("abba", "dog cat cat dog") is True
    assert s.wordPattern("abba", "dog cat cat fish") is False
    assert s.wordPattern("aaaa", "dog cat cat dog") is False
    assert s.wordPattern("abba", "dog dog dog dog") is False
    assert s.wordPattern("abc", "dog cat fish") is True
    assert s.wordPattern("abc", "dog cat") is False

    print("all tests passed")

test_word_pattern()
```

Test meaning:

| Test | Why |
|---|---|
| `"abba"`, `"dog cat cat dog"` | Valid bijection |
| `"abba"`, `"dog cat cat fish"` | Same letter maps to different words |
| `"aaaa"`, `"dog cat cat dog"` | One letter maps to several words |
| `"abba"`, `"dog dog dog dog"` | Several letters map to one word |
| `"abc"`, `"dog cat fish"` | All distinct and valid |
| `"abc"`, `"dog cat"` | Length mismatch |