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.
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:
- 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`, including `end_word`, must be in `word_list`. `begin_word` itself does not need to be in `word_list`, but it may be.
Return the number of words in the shortest such transformation sequence, counting both `begin_word` and `end_word` (a sequence of k steps contains k + 1 words). If `end_word` is not in `word_list`, or no sequence exists, return `0`. Several different sequences can share the shortest length; only that length is returned.
The answer is at most `len(word_list) + 1` (at most 5001), so it fits in a 32-bit integer in every language.
### 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 = "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.
### 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`.
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
Input: ('a', 'c', ['c'])
Expected Output: 2
Explanation: Minimum valid input: single-letter words and a one-word list; c is one step from a, so the sequence a -> c has 2 words.
Input: ('cat', 'cot', ['cut', 'cog'])
Expected Output: 0
Explanation: Source Example 3: cot is one step from cat but is missing from word_list, so no sequence can end at it.
Hints
- Two words can be consecutive in a sequence only when they agree at every position but one; reordering letters never counts as a step.
- begin_word does not have to be in word_list, but end_word does: settle that case before anything else.
- The answer counts words, not steps, and several different sequences can tie for the shortest length, so only the length matters.