Find the Minimum Word Transformation Steps

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

start_word = "hit"
end_word = "cog"
words = ["hot", "dot", "dog", "lot", "log", "cog"]
output = 4

One shortest sequence is hit -> hot -> dot -> dog -> cog.

Find the Minimum Word Transformation Steps

Hints

1. A breadth-first search gives the minimum number of one-character changes.
2. Generate neighbors one position at a time and mark dictionary words visited when enqueued.

Approach

Treat dictionary words as vertices connected when they differ in exactly one position. Run breadth-first search from the start word without needing to insert it into the dictionary. Generate neighbors by replacing each character with each lowercase letter and accept generated words still present in an unvisited dictionary set. Removing a word when it is enqueued prevents repeats. Breadth-first search visits transformations in nondecreasing change count, so the first discovery of the end word is minimum. If the end is absent initially or never discovered, return -1.

• Time complexity: O(V L 26) expected time, where V is the number of visited words and L is word length.
• Space complexity: O(N L) for the dictionary set and breadth-first queue.