A 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 the number of words in the shortest transformation sequence from beginWord
to endWord
, or 0
if no such sequence exists.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
Constraints:
-
1 <= beginWord.length <= 10
-
endWord.length == beginWord.length
-
1 <= wordList.length <= 5000
-
wordList[i].length == beginWord.length
-
beginWord
,endWord
, andwordList[i]
consist of lowercase English letters. -
beginWord != endWord
- All the words in
wordList
are unique.
SOLUTION:
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
n = len(beginWord)
wordList = set(wordList + [beginWord])
graph = {}
for word in wordList:
for i in range(n):
for c in "abcdefghijklmnopqrstuvwxyz":
currstr = word[0:i] + c + word[i+1:]
if currstr != word and currstr in wordList:
if word in graph:
graph[word].append(currstr)
else:
graph[word] = [currstr]
dist = {}
dist[beginWord] = 1
queue = [(beginWord, 1)]
visited = set()
i = 0
while i < len(queue):
curr, k = queue[i]
for j in graph.get(curr, []):
if j not in visited:
dist[j] = dist.get(curr, float('inf')) + 1
if j == endWord:
return k + 1
visited.add(j)
queue.append((j, k + 1))
i += 1
return 0
Top comments (0)