Quick Overview

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.

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.

Hints

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

Loading coding console...