class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
wordList=set(wordList)
res=[]
layer={beginWord:[[beginWord]]}
while layer:
newlayer=defaultdict(list)
for w in layer:
if w==endWord:
res.extend(k for k in layer[w])
else:
for i in range(len(w)):
for c in string.ascii_lowercase:
neww=w[:i]+c+w[i+1:]
if neww in wordList:
newlayer[neww]+=[j+[neww] for j in layer[w]]
wordList-=set(newlayer.keys())
layer=newlayer
return res
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
wordList=set(wordList)
if endWord not in wordList:
return []
wordList.add(beginWord)
wordDict=defaultdict(list)
for word in wordList:
for i in range(len(word)):
pattern = word[:i]+'*'+word[i+1:]
wordDict[pattern].append(word)
queue=deque([(beginWord,1)])
visited,adjList=defaultdict(set),defaultdict(list)
visited[beginWord]=0
numStep=1
while queue:
currWord,step=queue.popleft()
if currWord==endWord:
numStep=step
break
for i in range(len(currWord)):
pattern=currWord[:i]+'*'+currWord[i+1:]
if pattern in wordDict:
for word in wordDict[pattern]:
if word not in visited or visited[word]==step+1:
adjList[word].append(currWord)
if word not in visited:
queue.append((word,step+1))
visited[word]=step+1
if numStep==1:return []
result=[]
array=[endWord]
self.backtrack(result,array, numStep,beginWord,adjList)
return result
def backtrack(self,result,array,numStep,beginWord,adjList):
if len(array)==numStep and array[-1]==beginWord:
temp=array.copy()
result.append(temp[::-1])
return
for word in adjList[array[-1]]:
array.append(word)
self.backtrack(result,array,numStep,beginWord, adjList)
array.pop()卡内存用回溯写法
