Coding questions · Amazon

Find shortest transformation steps in a word graph

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.

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.

Word Ladder Length

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.

Hints

Start with a direct data structure representation.
Handle edge cases before the main loop.