一亩三分地论坛

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

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

[算法题] 求助Wildcard Matching

[复制链接] |试试Instant~ |关注本帖
Snake_tomoyo 发表于 2015-2-24 15:13:49 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 Snake_tomoyo 于 2015-2-24 15:15 编辑

https://oj.leetcode.com/problems/wildcard-matching/
https://oj.leetcode.com/discuss/21634/c-dp-solution
上面是原题,下面是discussion里面的一种dp解法,我完全理解不了转移方程(2)。。。
按我的理解,f(i,j)应该为真当且仅当f(m,j-1)有一个为真, 0<=m<=i,但他这种做法的转移方程不仅depends on f(i,j-1), 甚至还扯上了 f(i-1,j), 这是最让我疑惑的地方。。。
谢谢各位解答!


Linzertorte 发表于 2015-2-25 14:46:12 | 显示全部楼层
我写过一个帖子。是贪心的做法。
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-2-25 14:46:56 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| Snake_tomoyo 发表于 2015-2-27 00:06:20 | 显示全部楼层
Linzertorte 发表于 2015-2-25 14:46
http://www.1point3acres.com/bbs/thread-101201-1-1.html

感谢回复!
这题我已经用贪心过了,只是在看别人DP解法的时候实在理解不了转移方程于是就过来问了。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-2-28 14:49:24 | 显示全部楼层
你的想法是对的,只是没有将DP贯彻到底。那个帖子中的转移方程的意思是:

如果p(1, j)在最后一个字符是'*'的情况下能够匹配s(1, i-1),那么p(1, j)肯定也能匹配s(1, i),因为多出来的s(i)可以由最后一个'*'匹配,这种情况下最后一个'*'匹配至少一个字符。这种情况其实已经包含了几乎所有的f(m, j-1)的情况。

但是如果p(1, j)不能匹配s(1, i-1),那么p(1, j)很可能不能匹配s(1, i),  只有一种情况例外:就是p(1, j-1) 本身就能匹配s(1, i),这种情况下'*'匹配0个字符。

我说你没有把DP贯彻到底的意思是:如果你已经知道了f(1, j-1)到f(i - 1, j-1)这个范围内恰有一个为真,那么现在再加上f(i, j-1), 问你f(1, j-1)到f(i, j-1)范围内是否恰有一个为真,你完全不需要重新再去看f(1, j-1)到f(i - 1, j-1)这个范围了,而只需要检查f(i, j-1)就可以。至于之前的那个范围内是否有一个为真,你只需看f(i-1,j)就知道,因为f(i-1, j)为真是建立在f(1, j-1)到f(i-1, j)这个范围内恰有一值为真的前提上的。


上述两者只要能满足一点就说明p(1, j)能够匹配s(1, i)。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| Snake_tomoyo 发表于 2015-3-5 13:56:40 | 显示全部楼层
stellari 发表于 2015-2-28 14:49
你的想法是对的,只是没有将DP贯彻到底。那个帖子中的转移方程的意思是:

如果p(1, j)在最后一个字符是' ...

绕得好晕不过终于大概理解了*代表长度>0的情况了。。。

这是我头一次遇到感觉DP不如Greedy递归好理解的时候哈哈
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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