p***e
发帖数: 111 | | j**********3
发帖数: 3211 | | p***e
发帖数: 111 | 3 代码很难看，晚上有时间再修改。 同样单向bfs需要1200ms左右ac。
class Solution:
def ladderLength(self, start, end, dict):
dict.add(end)
current, distance, visited = [start], 1, {start:0}
bcurrent, bdistance, bvisited = [end], 1, {end:0}
while current and bcurrent:
pre, bpre,next, bnext = [], [], [], []
for word in current:
for i in xrange(len(word)):
left, right = word[:i], word[i + 1:]
for j in 'abcdefghijklmnopqrstuvwxyz':
candidate = left + j + right
if candidate in dict and candidate not in visited:
visited[candidate] = 0
next.append(candidate)
for word in next:
if word in bpre:
return distance + bdistance - 1
if word in bcurrent:
return distance + bdistance
pre, current, distance = current, next, distance + 1
for word in bcurrent:
for i in xrange(len(word)):
left, right = word[:i], word[i + 1:]
for j in 'abcdefghijklmnopqrstuvwxyz':
candidate = left + j + right
if candidate in dict and candidate not in bvisited:
bvisited[candidate] = 0
bnext.append(candidate)
for word in bnext:
if word in pre:
return distance + bdistance - 1
if word in current:
return distance + bdistance
bpre, bcurrent, bdistance = bcurrent, bnext, bdistance + 1
return 0
【在 j**********3 的大作中提到】
: 上代码
| l*********r
发帖数: 136 | |
|
