Word Ladder

# Word Ladder ## Difficulty Hard ## Tags `graph`, `bfs`, `string` ## Problem Statement Given two words, `begin_word` and `end_word`, and a dictionary `word_list`, find the shortest transformation sequence from `begin_word` to `end_word` such that: 1. Only one letter can be changed at a time. 2. Each transformed word must exist in the word list. Return the sequence of words representing the shortest transformation. If no such sequence exists, return an empty list. ## Constraints - All words have the same length. - All words contain only lowercase alphabetic characters. - `begin_word` and `end_word` are non-empty and are not the same. - `word_list` contains unique words. - 1 ≤ word length ≤ 10 - 1 ≤ word_list length ≤ 5000 ## Signatures ### Python ```python def find_ladder(begin_word: str, end_word: str, word_list: List[str]) -> List[str]: pass ``` ### Java ```java public class Solution { public List<String> find_ladder(String begin_word, String end_word, List<String> word_list) { return null; } } ``` ### Csharp ```csharp public class Solution { public IList<string> find_ladder(string begin_word, string end_word, IList<string> word_list) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: vector<string> find_ladder(string begin_word, string end_word, vector<string> word_list) { } }; ``` ### C ```c vector<char*> find_ladder(char* begin_word, char* end_word, vector<char*> word_list) { } ``` ### Ruby ```ruby def find_ladder(begin_word, end_word, word_list) end ``` ### Perl ```perl sub find_ladder { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def find_ladder(begin_word: String, end_word: String, word_list: List[String]): List[String] = { } } ``` ### Haskell ```haskell find_ladder :: ... -> ... find_ladder args = undefined ``` ### Clojure ```clojure (defn find_ladder [begin_word end_word word_list] ) ``` ### Scheme ```scheme (define (find_ladder begin_word end_word word_list) ) ``` ## Examples ### Example 1 **Input:** ``` begin_word = "hit" end_word = "cog" word_list = ["hot", "dot", "dog", "lot", "log", "cog"] ``` **Output:** ``` ["hit", "hot", "dot", "dog", "cog"] ``` **Explanation:** One shortest path is: hit → hot → dot → dog → cog (length 5). ### Example 2 **Input:** ``` begin_word = "hit" end_word = "cog" word_list = ["hot", "dot", "dog", "lot", "log"] ``` **Output:** ``` [] ``` **Explanation:** The end_word "cog" is not in word_list, so no transformation is possible. ### Example 3 **Input:** ``` begin_word = "a" end_word = "c" word_list = ["a", "b", "c"] ``` **Output:** ``` ["a", "b", "c"] ``` **Explanation:** a → b → c ## Hints 1. This is a shortest path problem on a graph. 2. Nodes are words; edges exist between words differing by exactly one character. 3. Use Breadth-First Search (BFS) to find the shortest path. 4. To find neighbors efficiently, try replacing each character position with 'a'-'z'.