#127
Word Ladder
hard· Graphsruns: 0A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence such that every adjacent pair differs by a single letter and every intermediate word is in wordList. 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. endWord must appear in wordList.
sign in to paste and practice your own solution
wpm 0acc 100%time 0:000 / 953
from collections import defaultdict, deque
class Solution:
def ladderLength(
self, beginWord: str, endWord: str, wordList: list[str]
) -> int:
if endWord not in wordList:
return 0
patterns = defaultdict(list)
for word in wordList + [beginWord]:
for i in range(len(word)):
pattern = word[:i] + "*" + word[i + 1 :]
patterns[pattern].append(word)
visited = {beginWord}
queue = deque([(beginWord, 1)])
while queue:
word, steps = queue.popleft()
if word == endWord:
return steps
for i in range(len(word)):
pattern = word[:i] + "*" + word[i + 1 :]
for neighbor in patterns[pattern]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, steps + 1))
return 0
click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause
desktop only
codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.
you can still browse problems and sections from your phone.