查看: 3702|回复: 16
收起左侧

Amazon : 字符串最短路径

  |只看干货 |刷题
头像被屏蔽

分享帖子到朋友圈
wwwyhx | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:Amazon : 寻找最大BST子结构大小
下一篇:经典问题 : 字符串的最大公共子序列
needyou 2011-5-19 01:16:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (87)
 
 
2% (2)    👎
我发现所有的题我都只会naive的方法,还是得等我们石溪的gooooopan来回答吧
回复

使用道具 举报

darksteel 2011-5-19 02:52:42 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
回复 2# needyou
回复

使用道具 举报

needyou 2011-5-19 09:49:50 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (87)
 
 
2% (2)    👎
回复 3# darksteel


    我今天被geometry日了
回复

使用道具 举报

darksteel 2011-5-19 13:06:45 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
回复 4# needyou
我也还有考试,感觉动力不足。。
回复

使用道具 举报

needyou 2011-5-19 13:11:13 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (87)
 
 
2% (2)    👎
回复  needyou
我也还有考试,感觉动力不足。。
darksteel 发表于 2011-5-19 13:06


来,给你打打气

你就是这个样子所以才是个ms,哈哈哈,够歹毒吧
回复

使用道具 举报

darksteel 2011-5-19 13:13:15 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
回复 6# needyou
{:4_83:}不太明白,不过我确实得复习明天上午的考试才行了。。
回复

使用道具 举报

darksteel 2011-5-19 13:21:50 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
字符串编辑距离本来是典型的DP问题,但要求都是字典里的单词就不太好办。我再想如果要求所有单词两两之间的路径,不妨就把整个字典建成一个无向图,任意两个可以通过一次编辑达到的单词之间存在边,然后就转化为求最短路径了。不过判断两个单词是否能通过编辑一次达到也不是那么直接,不知道有没有线性的方法
回复

使用道具 举报

头像被屏蔽
holyzz 2011-5-19 14:08:18 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

epic 2011-5-20 10:41:41 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
首先要建图,建图可以考虑用hash的方法,增加一个字符,比如*,表示任意值。
对于一个单词,比如说abcd,我们分别将*bcd,a*cd,ab*d,abc*(修改字符),*abcd,a*bcd,ab*cd,abc*d,abcd*(插入字符),bcd,acd,abd,abc(删除字符),插入hash表,如果已经存在了,则说明存在可一步到达的单词,将其连边

至于求最短路,可以使用启发式搜索,因为两个单词的长度为la和lb的话,修改次数<=max(la,lb),因此实际路径相比于单词量来说是非常非常小的
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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