Find the Minimum Word Transformation Steps
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
Transform a start word into an end word by changing exactly one character at a time. Every intermediate word and the end word must belong to the supplied dictionary. Return the minimum number of character changes.
## Function Contract
Implement `minimum_word_steps(start_word, end_word, words)` and return an integer.
## Rules
- All words have the same length and matching is case-sensitive.
- The start word does not need to appear in the dictionary.
- Return `0` when the start and end words are equal.
- Return `-1` when no valid transformation exists.
## Constraints
- `1 <= len(start_word) <= 20`.
- `0 <= len(words) <= 100000`.
- Words contain lowercase English letters and are unique.
## Examples
```text
start_word = "hit"
end_word = "cog"
words = ["hot", "dot", "dog", "lot", "log", "cog"]
output = 4
```
One shortest sequence is `hit -> hot -> dot -> dog -> cog`.
Overview: Compute the minimum number of one-character transformations between equal-length words when every intermediate word must belong to a supplied dictionary, returning failure when no path exists.
Transform start_word into end_word by changing exactly one character per step. Every intermediate word and the end word must belong to the supplied dictionary; the start word need not. All words have the same length, matching is case-sensitive, and dictionary words are unique lowercase strings. Return the minimum number of character changes, return 0 when start and end are equal, and return -1 when no valid transformation exists.
Constraints
- 1 <= len(start_word) = len(end_word) <= 20.
- 0 <= len(words) <= 100000.
- All dictionary words have the same length, contain lowercase English letters, and are unique.
- The start word need not appear in the dictionary, but every intermediate word and the end word must.
- Return 0 for equal endpoints and -1 when no transformation exists.
Examples
Input: ('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])
Expected Output: 4
Explanation: This is the source example; one shortest sequence changes four characters across four steps.
Input: ('same', 'same', [])
Expected Output: 0
Explanation: Equal start and end words require no changes even with an empty dictionary.
Hints
- A breadth-first search gives the minimum number of one-character changes.
- Generate neighbors one position at a time and mark dictionary words visited when enqueued.