LC 0126 [H] Word Ladder II - ALawliet/algorithms GitHub Wiki
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
ans = []
Q = deque([ [beginWord] ])
visited = set()
wordSet = set(wordList)
while Q:
curLayerWords = set()
# because we want to return all the paths, and not just 1, we need to track on a level/layer basis
for _ in range(len(Q)):
curList = Q.popleft()
lastWord = curList[-1]
if lastWord == endWord:
ans.append(curList)
# look for next layer of words
for i in range(len(beginWord)): # all words have same len
for c in string.ascii_lowercase: # a-z
nextWord = lastWord[:i] + c + lastWord[i+1:]
if nextWord in wordSet and nextWord not in visited:
Q.append(curList + [nextWord])
# visited.add(nextWord) # this will block the other paths
curLayerWords.add(nextWord) # so maintain it outside the level
visited.update(curLayerWords) # add set 2 to set 1 without returning a new set (update instead of union)
return ans