一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 337|回复: 3
收起左侧

[动态规划] 【Edit Distance】生成的数组是(m+1)*(n+1)和m*n真的有差别吗?

[复制链接] |试试Instant~ |关注本帖
小马3107 发表于 2015-8-11 10:40:33 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
和很多答案比了比,后半部分没有差别。
好吧我觉得错误并不在于生成的二维数组是m*n还是(m+1)*(n+1),而是在初始化的阶段。
我的逻辑是在二维数组的第一行和第一列中用字符串1的第一个字符和字符串2比,遇到相等的字符就不变,如果不同就把前面的数+1。
答案是构造二维数组(m+1)*(n+1),用空字符去比字符串1和2.
差别在哪?为什么我的答案就会出错呢?求拍醒。
EditDistance.jpg
stellari 发表于 2015-8-11 11:01:03 | 显示全部楼层
你这个逻辑不对,随便举个例子吧,比如:word1 = 'aaaaaaaa', word2 = 'aba'.
现在拿word2中的字符分别和word1的第一个字符‘a'比:

1. a == a  => start = 0; 正确
2. a != b => start = 1; 正确
3. a == a => start = 1; 错误!'a' 和 'aba'的distance应为2.

正确的逻辑是:“start不增加的循环最多出现一次”,即第二次出现a == a时就应该跳过。所以你还不如就用m+1,n+1的代码好了。
回复 支持 反对

使用道具 举报

 楼主| 小马3107 发表于 2015-8-11 11:15:45 | 显示全部楼层
stellari 发表于 2015-8-11 11:01
你这个逻辑不对,随便举个例子吧,比如:word1 = 'aaaaaaaa', word2 = 'aba'.
现在拿word2中的字符分别和w ...

好的。谢谢!
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-8-14 17:29:48 | 显示全部楼层
多加1个往往是为了让代码更好写,原理肯定是一样的。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 19:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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