正则表达式匹配
- 参与人数:660时间限制:1秒空间限制:32768K
- 通过比例:14.97%
- 最佳记录:0 ms|8552K(来自高鹏)
题目描述
链接:http://www.nowcoder.com/practice/45327ae22b7b413ea21df13ee7d6429c?rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题意:点可以表示任意字符,星*表示前一个字符可以出现0--n次,那么用递归来解,条件是str串和pattern串到达结尾,或者str串结尾了,pattern串没有结尾,都退出。
而递归的条件是:遇到*,则三个出口,(str+1,pattern+2),(str+1,(str,pattern);
遇到'.' (str+1,pattern+1);
#include<cstdio> using namespace std; class Solution { public: bool match(char* str,char* pattern) { // puts(str); // puts(pattern); if(str==NULL && pattern==NULL) return true; if(str==NULL || pattern==NULL) return false; return matchCore(str,pattern); } bool matchCore(char *str,char *pattern) { if(*str=='\0' && *pattern=='\0') {return true;} if(*str!='\0' && *pattern=='\0') return false; if(*(pattern+1)=='*') { if(*str==*pattern || (*pattern=='.'&&*str!='\0')) { //move on the next state return matchCore(str+1,pattern+2) //stay on the current state || matchCore(str+1,pattern) //ignore a '*' || matchCore(str,pattern+2); } else return matchCore(str,pattern+2); } if(*str==*pattern||(*pattern=='.'&&*str!='\0')) { return matchCore(str+1,pattern+1); } return false; } }; int main() { char ch1[]=""; char ga1[]=""; char *ch=ch1; char *ga=ga1; Solution so; if(so.match(ch,ga))printf("true\n"); else printf("false\n"); return 0; }