j*3
2 楼
上代码
p*e
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 的大作中提到】
: 上代码
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
4 楼
Mark!
相关阅读
有没有博士找工作不用presentation的？google还找被拒的参加survey啊请教个 interview question问个问题关于java data structure的如何拖延电话面试的时间？同学们 Opt approved 之后几天能收到卡呀？请问AECOM工作的xdjms，现在还办H1B吗？ (转载)这样的情况要不要写follow up letter能不能用据了的offer letter申请opt 加急？take a break, and try this small test (20 questions)明天面MS onsite, 求祝福！background check是在什么时候？包子求助——H1b 申请递交后的身份!!!这周H1B petition 长得挺多拿ME和MS有区别吗？正式offer, 一般是HR还是hiring manager发?need web tester有人面过smith international吗？an intern offer and some other questions有关OPT延期