【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 259|回复: 1
收起左侧

[Leetcode] LeetCode上Word Ladder II目前最快的C++解法

[复制链接] |试试Instant~ |关注本帖
magicsets 发表于 2017-7-4 22:55:21 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
比LeetCode上次快的解法快25%左右... 而且与99.9%的“标准答案”的C++/Java解法思路不太一样,考虑到这道题比较有名,还是分享(得瑟)一下 ,也为大家扩展一下思路。

这个问题本质上是求图上两点之间的所有的最短路径,难度在于图不是预先给好的,所以就有两种做法:
(1) 不预先构造图,而是对所有BFS过程中正在访问的点,“测试”其是不是有边通向其他节点,就是几乎所有答案中都会出现的如下循环:
for (char c = 'a';  c <= 'z'; ++c) {
   ...
}
这一类答案这里就不贴了,搜索Word Ladder II找到的都是的。

(2)预先构造图,然后对构造好的图用BFS。
这种方法BFS的过程非常快,hotspot在于构造图的过程 -- 用O(n^2)的嵌套循环两两比较字符串基本上一定会超时。

然而我们仍然可以用HashMap在O(n)时间内构造出图来,具体的实现参见代码里的initEdges()实现。
不过,只用HashMap的实现,速度实际上是比方法(1)要慢的,这与LeetCode的测试数据的性质有关。

所加了另外两个根据数据性质而调用的“fast path“ -- initEdgesCompCode()/initEdgesCompCodePos(),将长度小于8的字符串解释成无符号整数,这样就一定程度上实现了所谓“Bit-level parallelism”,速度也快了好几倍。

代码在这里:
https://github.com/jqdocshare/docs/blob/master/WordLadderII.cpp

wl.png




brn 发表于 2017-7-5 12:17:59 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
说白了就是离散化呗
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-22 19:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表