Find shortest transformation steps in a word graph

Q: 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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.