ALG-H008HardGraph Traversal
One-Letter Word Route
Transform start into end by changing exactly one lowercase letter per step; every intermediate word and end must appear in dictionary. Return the number of words in the shortest sequence, including endpoints; return 0 if impossible. If start equals end, return 1.
Contract
input start: string
input end: string
input dictionary: string[]
return integer
Constraints
- • All words lowercase a-z
- • All words have equal length
- • Word length <= 12
Examples
Example 1
start = "hit"
end = "cog"
dictionary = ["hot", "dot", "dog", "lot", "log", "cog"]
→ 5
Example 2
start = "hit"
end = "cog"
dictionary = ["hot", "dot", "dog", "lot", "log"]
→ 0
5 judge tests (2 shown above). Target complexity: BFS; roughly O(dictionary_size * word_length * alphabet_size).