s*****n
发帖数: 994 | 1 为什么在test bench里面这组是match的？
isMatch("aab", "c*a*b") → true |
j*****y
发帖数: 1071 | 2 c* 表示可以用多个 c 或者 0 个 c
a* 表示可以用多个 a 或者 0 个 a
感觉这种匹配方式在现有的系统里面没见过。
【在 s*****n 的大作中提到】
: 为什么在test bench里面这组是match的？
: isMatch("aab", "c*a*b") → true
|
f*******t
发帖数: 7549 | 3 没见过？这是标准正则表达式的规则呀
【在 j*****y 的大作中提到】
: c* 表示可以用多个 c 或者 0 个 c
: a* 表示可以用多个 a 或者 0 个 a
: 感觉这种匹配方式在现有的系统里面没见过。
|
j*****y
发帖数: 1071 | 4 呵呵, 很少用过 正则表达式， 惭愧, 学业不精阿 :)
【在 f*******t 的大作中提到】
: 没见过？这是标准正则表达式的规则呀
|
d**********x
发帖数: 4083 | 5 read first 5 chapters in Mastering Regular Expression...
it's good for your daily work.
【在 j*****y 的大作中提到】
: 呵呵, 很少用过 正则表达式， 惭愧, 学业不精阿 :)
|
j*****y
发帖数: 1071 | 6 thanks.
【在 d**********x 的大作中提到】
: read first 5 chapters in Mastering Regular Expression...
: it's good for your daily work.
|
s*****n
发帖数: 994 | 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*****n
发帖数: 994 | 8 只是不知道为什么大case会爆runtime的错？ |
