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.
(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".