t********n
发帖数: 611 | 1 还是不够快的问题，自己机器上测试结果正确，用了BFS and DFS，不知道还能怎样改
进，请牛牛们指教！
Python code:
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return a list of lists of string
def findLadders(self, start, end, dict):
def buildPath(end, start, path= []):
path += [end]
if end == start:
path.reverse()
result.append(path)
else:
for p in parents[end]:
newPath = path[:]
buildPath(p, start, newPath)
d = set(dict)
d.add(start)
d.add(end)
parents = {start:None}
current = set([start])
result = []
while current !=[]:
next = set()
for word in current:
for i in xrange(len(word)):
left, right = word[:i], word[i+1:]
for l in "abcdefghijklmnopqrstuvwxyz":
newWord = left + l + right
if newWord != word and newWord != start and newWord
not in current:
if newWord in d:
next.add(newWord)
if newWord not in parents:
parents[newWord] = set([word])
else:
if newWord not in parents[word]:
parents[newWord].add(word)
if end in next:
break
else:
current = next
buildPath( end, start)
return result | t********n
发帖数: 611 | 2 过了， 参考了某位高人的代码，每次找下级词汇前，把这一级从字典里删除，立刻快
了很多。
Code:
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return a list of lists of string
def findLadders(self, start, end, dict):
def buildPath(end, start, path= []):
# print
# print "path at beginning:", path
path += [end]
if end == start:
path.reverse()
result.append(path)
else:
for p in parents[end]:
newPath = path[:]
# print "for child ", p, " path is :", newPath
buildPath(p, start, newPath)
d = set(dict)
d.add(start)
d.add(end)
length = len(start)
parents = {}
for word in d:
parents[word] = []
result = []
candidates = [set(), set()]; current=0; previous = 1
candidates[current].add(start)
while True:
previous, current = current, previous
for word in candidates[previous]: d.remove(word)
candidates[current].clear()
for word in candidates[previous]:
# print "word now:", word
for i in xrange(length):
left, right = word[:i], word[i+1:]
for l in "abcdefghijklmnopqrstuvwxyz":
if word[i] != l:
newWord = left + l + right
if newWord in d:
candidates[current].add(newWord)
# print "newWord now:", newWord
# print "in parents?: ", newWord in parents
parents[newWord].append(word)
if len(candidates[current]) == 0: return result
if end in candidates[current]:
break
# print "parents:", parents
buildPath( end, start)
return result
【在 t********n 的大作中提到】
: 还是不够快的问题，自己机器上测试结果正确，用了BFS and DFS，不知道还能怎样改
: 进，请牛牛们指教！
: Python code:
: class Solution:
: # @param start, a string
: # @param end, a string
: # @param dict, a set of string
: # @return a list of lists of string
: def findLadders(self, start, end, dict):
: def buildPath(end, start, path= []):
|
|
