leetcode regular expression match的问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

leetcode regular expression match的问题

leetcode regular expression match的问题# JobHunting - 待字闺中

s*n2013-01-29 08:01

1 楼

为什么在test bench里面这组是match的？
isMatch("aab", "c*a*b") → true

j*y2013-01-29 08:01

2 楼

c* 表示可以用多个 c 或者 0 个 c
a* 表示可以用多个 a 或者 0 个 a
感觉这种匹配方式在现有的系统里面没见过。

【在 s*****n 的大作中提到】

: 为什么在test bench里面这组是match的？
: isMatch("aab", "c*a*b") → true

f*t2013-01-29 08:01

3 楼

没见过？这是标准正则表达式的规则呀

【在 j*****y 的大作中提到】

: c* 表示可以用多个 c 或者 0 个 c
: a* 表示可以用多个 a 或者 0 个 a
: 感觉这种匹配方式在现有的系统里面没见过。

j*y2013-01-29 08:01

4 楼

呵呵, 很少用过正则表达式，惭愧, 学业不精阿 :)

【在 f*******t 的大作中提到】

: 没见过？这是标准正则表达式的规则呀

d*x2013-01-29 08:01

5 楼

read first 5 chapters in Mastering Regular Expression...
it's good for your daily work.

【在 j*****y 的大作中提到】

: 呵呵, 很少用过正则表达式，惭愧, 学业不精阿 :)

j*y2013-01-29 08:01

6 楼

thanks.

【在 d**********x 的大作中提到】

: read first 5 chapters in Mastering Regular Expression...
: it's good for your daily work.

s*n2013-01-29 08:01

7 楼

多谢各位，刚才把regular expression match理解为wildcard matching了，
那就顺便把wildcard matching的code给贴上来吧
class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int m=strlen(s);
int n=strlen(p);
bool dp[1000][1000] = {false};//dp[i][j] means last i chars in s
matches last j chars in p
dp[0][0] = true;
for (int i=1; i<=n; ++i){
dp[0][i] = dp[0][i-1]&&*(p+n-i)=='*'?true:false;
}
for (int i=1; i<=m; ++i){
dp[i][0] = false;
}
for (int i=1; i<=n; ++i){
char p_c = *(p+n-i);
for (int j=1; j<=m; ++j){
char s_c = *(s+m-j);
if (p_c == '*'){
for (int k=0; k<=j; ++k){
dp[j][i] = dp[j][i] || dp[k][i-1];
}
}else if (p_c == '?' || p_c==s_c){
dp[j][i] = dp[j-1][i-1];
}else{
dp[j][i] = false;
}
}
}
return dp[m][n];
}
};

s*n2013-01-29 08:01

8 楼

只是不知道为什么大case会爆runtime的错？