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!
相关阅读
怎么有那么多东西要准备的？Cat on-site 求 bless要换工作了，要不要把休假用完？opt extension的EAD card已经拿到了，立刻quit工作没问题吧？悲剧，on-site回来7周了，又通知去二进宫N现在疯狂招人吗？咨询加州小公司面试问题帮我的老美朋友找网络兼职。。。求英文远程教学的国内推广。。。康州小公司，10W 够吗提供湾区职业社交网络L内推G家面经HR说安排电面，但是又没消息了同学们，找工作不要光看base， bonus也很重要看版上的帖子就一个感想申MS如果被拒了，会不会留下记录投同家公司不同position的问题Find consecutive repeated stringE-verify的公司得多大啊？求ASIC相关工作的referSAS developer opening， DC area (转载)