Find shortest transformation steps in a word graph
Company: Amazon
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two strings `begin` and `end` of the same length, and a list `words` of distinct strings (also same length).
You can transform one string into another by changing **exactly one character** at a time. Each intermediate string (after each single-character change) must exist in `words`. The transformation can stop once you reach `end`.
### Task
Return the **minimum number of transformations** required to convert `begin` into `end` (counting each single-character change as 1). If it is impossible, return `-1`.
### Input
- `begin`: string
- `end`: string
- `words`: list of strings
### Output
- Integer: minimum number of single-character transformations, or `-1` if unreachable.
### Constraints (assume typical interview constraints)
- `1 ≤ len(begin) = len(end) ≤ 20`
- `1 ≤ len(words) ≤ 50_000`
- All strings contain only lowercase English letters.
### Example
- `begin = "hit"`, `end = "cog"`
- `words = ["hot","dot","dog","lot","log","cog"]`
- Output: `4` (hit→hot→dot→dog→cog)
Explain your approach and complexity.
Quick Answer: This question evaluates a candidate's ability to model string transformations as a graph, apply graph traversal and shortest-path reasoning, and manage efficient string-based search and data-structure choices within the Coding & Algorithms domain.
Return the length of the shortest sequence from begin_word to end_word, changing one character per step and using dictionary words. Return 0 if impossible.
Constraints
- Inputs are provided as Python literals compatible with the function signature.
- Return a deterministic value exactly matching the requested output.
Examples
Input: ('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])
Expected Output: 5
Explanation: Reachable ladder.
Input: ('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])
Expected Output: 0
Explanation: End missing.
Input: ('a', 'c', ['a', 'b', 'c'])
Expected Output: 2
Explanation: Single character words.
Hints
- Start with a direct data structure representation.
- Handle edge cases before the main loop.