由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 双向bfs果然有效率,pyhon 664ms 过wordladder I
相关主题
leetcode wordladder2 求助!(solved)IF语句&&前后换个顺序就超时!!!搞笑啊!!!
求讨论关于Leetcode的WordLadder I的DFS解法Google 店面
问个BFS leetcodeLeetCode: Word Ladder
问两道面试中碰到的题目wordbreak in C?
Amazon电面纪实Course Schedule II DFS版
Word Ladder几个test case 没看明白求bless
问一个word ladder的题目再来问一下word search的时间复杂度分析
Time limit exceeded for Word Ladder(leetcode)请教Word Search II那题的复杂度
相关话题的讨论汇总
话题: word话题: bdistance话题: candidate话题: bcurrent话题: distance
进入JobHunting版参与讨论
1 (共1页)
p***e
发帖数: 111
1
就是代码丑了一些,重复部分好多。
j**********3
发帖数: 3211
2
上代码
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
4
Mark!
1 (共1页)
进入JobHunting版参与讨论
相关主题
请教Word Search II那题的复杂度Amazon电面纪实
本版目前为止的所有ebay面经及答案Word Ladder几个test case 没看明白
请问leetcode wordladder题什么意思?问一个word ladder的题目
不明白leetcode OJ wordladder 2 总是 Time Limit ExceededTime limit exceeded for Word Ladder(leetcode)
leetcode wordladder2 求助!(solved)IF语句&&前后换个顺序就超时!!!搞笑啊!!!
求讨论关于Leetcode的WordLadder I的DFS解法Google 店面
问个BFS leetcodeLeetCode: Word Ladder
问两道面试中碰到的题目wordbreak in C?
相关话题的讨论汇总
话题: word话题: bdistance话题: candidate话题: bcurrent话题: distance