Word Ladder Shortest Sequence

MediumPython

Problem

An Adobe Photoshop text workflow needs to transform a starting keyword into a target keyword using only approved intermediate words. Implement a Breadth-First Search solution that returns the shortest valid transformation sequence.

A transformation changes exactly one lowercase character. Every intermediate word, including the target, must appear in word_list. Each word has the same length as start_word. Return the sequence of words from start_word to end_word, or an empty list if no sequence exists.

Formal Specification

Implement ladder_path(start_word, end_word, word_list).

Input: start_word and end_word are strings. word_list is a list of unique lowercase strings.
Output: Return a list of strings representing the shortest valid path. If multiple shortest paths exist, return any one of them.
If start_word == end_word, return [start_word], even if it is not in word_list.

Constraints

1 <= len(start_word) == len(end_word) <= 10
1 <= len(word_list) <= 5 * 10^3
Every word contains only lowercase English letters
All words in word_list are unique

Function Signature

def ladder_path(start_word, end_word, word_list):

Formal Specification

Implement ladder_path(start_word, end_word, word_list).

Input: start_word and end_word are strings. word_list is a list of unique lowercase strings.
Output: Return a list of strings representing the shortest valid path. If multiple shortest paths exist, return any one of them.
If start_word == end_word, return [start_word], even if it is not in word_list.