Core Insight A visited structure makes each vertex’s work happen at most once.
Common Pitfall Mark a node visited when it is scheduled, not after duplicate work is queued.
Description
Find shortest transformation sequence from beginWord to endWord.
Constraints
- Time Complexity:
O(n·m²) - Space Complexity:
O(n·m²)
Tags
hash-mapstringbfs
Implementation Plan Translate the invariant into these small, testable moves.
- Choose a start node or component.
- Add it to the traversal frontier.
- Visit valid unseen neighbors.
- Repeat for every remaining component if needed.
def ladderLength(beginWord, endWord, wordList):
if endWord not in wordList:
return 0
nei = collections.defaultdict(list)
wordList.append(beginWord)
for word in wordList:
for j in range(len(word)):
pattern = word[:j] + "*" + word[j + 1:]
nei[pattern].append(word)
visit = set([beginWord])
q = collections.deque([beginWord])
res = 1
while q:
for i in range(len(q)):
word = q.popleft()
if word == endWord:
return res
for j in range(len(word)):
pattern = word[:j] + "*" + word[j + 1:]
for neiWord in nei[pattern]:
if neiWord not in visit:
visit.add(neiWord)
q.append(neiWord)
res += 1
return 0