Katkat
Back

Find shortest transformation steps in a word graph

AmazonApplied Scientist · Technical Screen
MediumApplied ScientistTechnical ScreenCoding & Algorithms

Last updated

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.