LeetCode 솔루션 분류
[8/14] 126. Word Ladder II
본문
Hard
4650587Add to ListShareA transformation sequence from word beginWord
to word endWord
using a dictionary wordList
is a sequence of words beginWord -> s1 -> s2 -> ... -> sk
such that:
- Every adjacent pair of words differs by a single letter.
- Every
si
for1 <= i <= k
is inwordList
. Note thatbeginWord
does not need to be inwordList
. sk == endWord
Given two words, beginWord
and endWord
, and a dictionary wordList
, return all the shortest transformation sequences from beginWord
to endWord
, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [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.
Constraints:
1 <= beginWord.length <= 5
endWord.length == beginWord.length
1 <= wordList.length <= 500
wordList[i].length == beginWord.length
beginWord
,endWord
, andwordList[i]
consist of lowercase English letters.beginWord != endWord
- All the words in
wordList
are unique.
Accepted
326,866
Submissions
1,183,724
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
wordList = set(wordList)
if endWord not in wordList:
return []
# BFS visit
curr_level = {beginWord}
parents = collections.defaultdict(list)
while curr_level:
wordList -= curr_level
next_level = set()
for word in curr_level:
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word in wordList:
next_level.add(new_word)
parents[new_word].append(word)
if endWord in next_level:
break
curr_level = next_level
# DFS reconstruction
res = []
def dfs(word, path):
if word == beginWord:
path.append(word)
res.append(path[::-1])
else:
for p_word in parents[word]:
dfs(p_word, path + [word])
dfs(endWord, [])
return res