#126

Word Ladder II

international master · 2045 · lc hard +32 · verified · 27.6% accepted · 6,533 likes · top 6%

Description

A transformation sequence from beginWord to endWord using dictionary wordList is a chain beginWord -> s1 -> s2 -> ... -> sk where:

- Each consecutive pair of words differs by exactly one letter.

- Every intermediate word si (for 1 <= i <= k) must appear in wordList. The beginWord does not need to be in wordList.

- sk == endWord

Return all shortest transformation sequences from beginWord to endWord, or an empty list if none exist. Each sequence should be given as [beginWord, s1, s2, ..., sk].

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

Explanation: There are 2 shortest transformation sequences:

"hit" -> "hot" -> "dot" -> "dog" -> "cog"

"hit" -> "hot" -> "lot" -> "log" -> "cog"

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Code

1

2

3

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]: