class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
if endWord not in wordList or not beginWord or not endWord or not wordList:
return []
def maskWord(word, i=0):
return word[:i] + '*' + word[i+1:]
L = len(beginWord)
table = defaultdict(list)
for i in range(L):
for word in wordList:
table[maskWord(word, i)].append(word)
q = deque([(beginWord, [beginWord])])
seen = set([beginWord])
ans = []
while q:
size = len(q)
local = set()
for i in range(size):
word, path = q.popleft()
for j in range(L):
for next_word in table[maskWord(word, j)]:
if next_word == endWord:
ans.append(list(path + [next_word]))
if next_word not in seen:
q.append((next_word, path + [next_word]))
local.add(next_word)
if ans:
break
seen = seen.union(local)
return ans