今天尝试做一道正则表达式判断的String题目, 同时温习一下C语言的使用
题目
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
- '.' Matches any single character.
- '*' Matches zero or more of the preceding element.
- The matching should cover the entire input string (not partial).
Note:
- s could be empty and contains only lowercase letters a-z.
- p could be empty and contains only lowercase letters a-z, and characters like . or *.
题解
这是一段错误的代码, 其思维是线性的; 而在编译原理学正则表达式的时候,我们往往需要构建分析树, 这说明一个语言(这里当然不是指编程语言)在做正则化判断时候不能单纯线性地去考虑, 而且树的形状也应该很容易想到递归才是.
bool isMatch(char* s, char* p) {
char last = 0;
while(*p != 0){
if(*p == '*'){
if(*s == last || last == '.')
p--;
else
s--;
}
else if(*(p+1) == '*'){
last = *p;
s--;
}
else if(*p != '.' && *p != *s){
break;
}
p++;
s++;
}
return (*p == 0 && *s == 0);
}
第二版本的代码如下, 采用了递归, 通过了(在几次试错之下)
bool isMatch(char* s, char* p) {
// printf("test: [%s] [%s]\n", s, p);
if(*p == 0 && *s == 0) return true;
else if(*(p+1) == '*'){
if(isMatch(s, p+2)) return true;
while(*s == *p || (*p == '.' && *s != 0)){
if(isMatch(++s,p+2)) return true;
}
}
else if(*s == *p || (*p == '.' && *s != 0)){
return isMatch(s+1, p+1);
}
return false;
}
万万没想到: 这题也是可以用动态规划来做,而且效率很高:
解析 (这个思路真的挺有深度的,值得多次回顾)
