Shortest One-Letter-at-a-Time Transformation Between Two Words
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two words, `begin_word` and `end_word`, and a list of words `word_list`. All of the words have the same length and consist of lowercase English letters. Transform `begin_word` into `end_word` one step at a time: each step changes exactly one letter, and every word produced along the way, including `end_word`, must appear in `word_list`. Return the number of words in the shortest such transformation sequence, counting both `begin_word` and `end_word`, or `0` if no sequence exists.
### Function Signature
```python
def shortest_transformation_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
```
### Rules
- One step replaces the letter at exactly one position with a different letter. Letters are never inserted, deleted or reordered.
- Every word after `begin_word` must be in `word_list`. `begin_word` itself does not need to be in `word_list`, but it may be.
- If `end_word` is not in `word_list`, return `0`.
- The answer counts words, not steps: a sequence of k steps contains k + 1 words.
### Constraints
- `1 <= len(begin_word) <= 10`
- `len(end_word) == len(begin_word)`, and every word in `word_list` has that same length.
- `begin_word != end_word`
- `1 <= len(word_list) <= 5000`, and the words in `word_list` are distinct.
- Every word consists only of the lowercase letters `a` to `z`.
- The answer is an integer between `0` and `len(word_list) + 1`.
### Examples
**Example 1**
```text
Input: begin_word = "cold", end_word = "warm",
word_list = ["cord", "word", "worm", "card", "ward", "warm", "wild"]
Output: 5
```
`cold -> cord -> card -> ward -> warm` takes four steps, so the sequence has 5 words. `cold -> cord -> word -> worm -> warm` is another sequence of the same length. Nothing shorter exists, because `cold` and `warm` differ in all four positions.
**Example 2**
```text
Input: begin_word = "lead", end_word = "gold", word_list = ["load", "gold"]
Output: 0
```
`lead` can become `load`, but `load` differs from `gold` in two positions and `lead` differs from it in three, so `gold` cannot be reached.
**Example 3**
```text
Input: begin_word = "cat", end_word = "cot", word_list = ["cut", "cog"]
Output: 0
```
`cot` is one step from `cat`, but it is not in `word_list`, so no valid sequence ends at it.
Overview: Find the number of words in the shortest chain that turns a start word into a target word by changing exactly one letter per step, where every intermediate word and the target must come from a given word list. It tests modeling words as an implicit graph and finding a shortest path efficiently.