def findLadders(self, beginWord, endWord, wordList):
:type beginWord: str
:type endWord: str
:type wordList: List[str]
wordSet = set()
for word in wordList:
level = set([beginWord])
parents = collections.defaultdict(set)
while level and endWord not in parents:
next_level = collections.defaultdict(set)
for word in level:
for i in range(len(beginWord)):
p1 = word[:i]
p2 = word[i+1:]
for j in 'abcdefghijklmnopqrstuvwxyz':
if word[i] != j:
childWord = p1 + j + p2
if childWord in wordSet and childWord not in parents:
level = next_level
res = [[endWord]]
while res and res !=beginWord:
res = [[p]+r for r in res for p in parents[r]]
Could you please point out what's the main adds-up in this solution to the solution of Word Ladder I? Thanks.
Compare to the other solutions, I think yours only adds-up only a little on the solution of Word Ladder I.
I think your main difference to the other solutions of is the way you build the path from the tree, while the others recorded the whole path (so far) in each step, and each step they have to copy over, am I right? But the only short coming of the tree is that you might have to visit some tree nodes that don't go to the end word.
One thing I did not get earlier in the code is that this visited set is used to record visited words in current level of the BFS queue. by removing visited words from the wordSet, in next level we will not have previous visited words.
(continue my previous comment): by "bad" predecessors I mean the following: vertex "firstword" can "relax" vertex "thirdword" by settign distance of vertex "thirdword" to 5. Thus, we add ""firstword" to the prev List ot "thirdword". BUT on the next steps we may have vertex "therdword", which will relax vertex "thirdword" to 1. At this point I think that we should remove "firstword" from the prev list and to add just "therdword".