# LeetCode 127: Word Ladder

## Problem Restatement

We are given:

| Name | Meaning |
|---|---|
| `beginWord` | Starting word |
| `endWord` | Target word |
| `wordList` | Dictionary of allowed words |

We may transform one word into another by changing exactly one character.

Every transformed word must exist in `wordList`.

We need to return the number of words in the shortest transformation sequence from `beginWord` to `endWord`.

If no valid sequence exists, return `0`.

## Examples

Example 1:

```python
beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
```

One shortest sequence is:

```text
hit -> hot -> dot -> dog -> cog
```

Length:

```python
5
```

Another shortest sequence also exists:

```text
hit -> hot -> lot -> log -> cog
```

The answer is still `5` because we only need the shortest length.

Example 2:

```python
beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log"]
```

Output:

```python
0
```

Because `"cog"` does not exist in `wordList`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `beginWord`, `endWord`, `wordList` |
| Output | Integer length of shortest transformation |
| Rule | Change exactly one letter at a time |
| Dictionary rule | Every intermediate word must exist in `wordList` |

Function shape:

```python
class Solution:
    def ladderLength(
        self,
        beginWord: str,
        endWord: str,
        wordList: list[str],
    ) -> int:
        ...
```

## Graph Interpretation

Think of each word as a node in a graph.

Two words are connected if they differ by exactly one character.

For example:

```text
hot -> dot
hot -> lot
dot -> dog
lot -> log
dog -> cog
log -> cog
```

The problem becomes:

Find the shortest path from `beginWord` to `endWord`.

Because every edge has equal weight, BFS is the correct algorithm.

## Why BFS Works

Breadth-first search explores nodes level by level.

Level meaning:

| Level | Meaning |
|---|---|
| 1 | Words reachable in one step |
| 2 | Words reachable in two steps |
| 3 | Words reachable in three steps |

The first time BFS reaches `endWord`, we know that path is shortest.

That is the main reason BFS is used here instead of DFS.

## Brute Force Idea

A brute force solution could try every possible transformation recursively.

That becomes extremely expensive because the number of paths grows rapidly.

Instead, BFS avoids exploring long unnecessary paths.

As soon as we reach `endWord`, we stop immediately.

## Key Insight

For each word, we can generate all possible one-letter transformations.

Suppose the current word is:

```python
"hot"
```

Possible one-letter mutations include:

```text
aot
bot
cot
...
hat
hbt
...
hoa
hob
...
```

Most are invalid.

We only keep words that exist in `wordList`.

To make lookup fast, store all dictionary words in a set:

```python
word_set = set(wordList)
```

Set lookup is approximately `O(1)`.

## Algorithm

First, convert the dictionary into a set.

If `endWord` is missing, return `0`.

Then start BFS from `beginWord`.

The queue stores:

```python
(word, distance)
```

For every word:

1. Try changing each character position.
2. Replace it with every letter from `'a'` to `'z'`.
3. If the generated word exists in the set:
   - add it to the queue
   - remove it from the set
4. If the generated word equals `endWord`, return the distance immediately.

Removing visited words is important.

Without it, BFS may revisit the same word many times.

## Correctness

BFS processes words in increasing order of transformation length.

At distance `1`, it visits all words reachable in one change.

At distance `2`, it visits all words reachable in two changes.

This continues until `endWord` is found.

Because BFS explores shorter paths before longer ones, the first time we reach `endWord` must correspond to the shortest possible sequence.

The algorithm only moves to valid dictionary words differing by one character, so every generated path is valid.

Therefore, the returned distance is exactly the shortest transformation length.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `n` | Number of words |
| `m` | Length of each word |

For every visited word:

- we try `m` positions
- for each position, we try `26` letters

So the total work is approximately:

```python
O(n * m * 26)
```

Simplified:

```python
O(n * m)
```

Space usage:

| Metric | Value |
|---|---|
| Time | `O(n * m)` |
| Space | `O(n * m)` |

The queue and set may both contain many words.

## Implementation

```python
from collections import deque

class Solution:
    def ladderLength(
        self,
        beginWord: str,
        endWord: str,
        wordList: list[str],
    ) -> int:
        word_set = set(wordList)

        if endWord not in word_set:
            return 0

        queue = deque([(beginWord, 1)])

        if beginWord in word_set:
            word_set.remove(beginWord)

        while queue:
            word, steps = queue.popleft()
            chars = list(word)

            for i in range(len(chars)):
                original = chars[i]

                for code in range(ord("a"), ord("z") + 1):
                    chars[i] = chr(code)
                    next_word = "".join(chars)

                    if next_word == endWord:
                        return steps + 1

                    if next_word not in word_set:
                        continue

                    word_set.remove(next_word)
                    queue.append((next_word, steps + 1))

                chars[i] = original

        return 0
```

## Code Explanation

We first convert the dictionary into a set:

```python
word_set = set(wordList)
```

This makes lookup fast.

Then we handle the impossible case:

```python
if endWord not in word_set:
    return 0
```

The BFS queue stores:

```python
(word, steps)
```

Example:

```python
("hit", 1)
```

means:

“We are currently at `"hit"` and the sequence length is `1`.”

For each character position:

```python
for i in range(len(chars)):
```

we try replacing it with all letters:

```python
for code in range(ord("a"), ord("z") + 1):
```

Then we rebuild the candidate word:

```python
next_word = "".join(chars)
```

If it matches `endWord`, we immediately return:

```python
steps + 1
```

Otherwise, if it exists in the dictionary:

```python
if next_word in word_set:
```

we:

1. mark it visited
2. push it into the queue

```python
word_set.remove(next_word)
queue.append((next_word, steps + 1))
```

Removing visited words prevents repeated processing.

## Testing

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

    assert s.ladderLength(
        "hit",
        "cog",
        ["hot", "dot", "dog", "lot", "log", "cog"],
    ) == 5

    assert s.ladderLength(
        "hit",
        "cog",
        ["hot", "dot", "dog", "lot", "log"],
    ) == 0

    assert s.ladderLength(
        "a",
        "c",
        ["a", "b", "c"],
    ) == 2

    assert s.ladderLength(
        "hot",
        "dog",
        ["hot", "dog"],
    ) == 0

    assert s.ladderLength(
        "red",
        "tax",
        ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"],
    ) == 4

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Verifies normal BFS behavior |
| Missing `endWord` | Impossible case |
| Single-character words | Smallest valid transformation |
| No connecting path | Graph disconnected |
| Multiple valid paths | Confirms shortest distance is returned |