Coursera 店面

bulletthinking

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

猎头联系和coursera牵上了线。

店面是字符匹配，利口正则表达式的变种。不同的地方是：

1. 只要text中有某一个substring符

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

;, P: "at?t?x?e" => true

drifterWendy

想请问除了枚举given string的所有substring然后match以外（runtime会O(n^4)）还有更快的方法吗

pip3go · 2019-10-30 01:47:35

想问问楼主第二题怎么做的～

bulletthinking · 2019-10-30 01:49:41

pip3go 发表于 2019/10/30 01:47:35
想问问楼主第二题怎么做的～

dp啊，和离口的正则表达式那题很像

pip3go · 2019-10-30 01:52:13

bulletthinking 发表于 2019-10-30 01:49
dp啊，和离口的正则表达式那题很像

二维DP就能解决嘛，还是需要三维～

bulletthinking · 2019-10-30 01:54:51

pip3go 发表于 2019/10/30 01:52:13
二维DP就能解决嘛，还是需要三维～

2维就可以了

Eeeva

感谢题主分享！

匿名用户-HLWTV *2021-12-3 05:21:34* · 2021-12-3 05:21:34

請問第三題複雜度 O(m * m * n ) 可以嗎，還是說就算是找 substring 也有 O(m * n) 的解法呢？