首页 > 代码库 > 【LeetCode】Regular Expression Matching
【LeetCode】Regular Expression Matching
Regular Expression Matching
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).The function prototype should be:bool isMatch(const char *s, const char *p)Some examples:isMatch("aa","a") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("aab", "c*a*b") → true
比较与Wildcard Matching的关系。
在Wildcard Matching中的‘?‘与此题的‘.‘一致。
但是Wildcard Matching中‘*‘本身代表通配符，而此题‘*‘代表前一个字符重复0或若干次。
class Solution {public: bool isMatch(const char *s, const char *p) { if(*p == 0) { if(*s == 0) return true; else return false; } //to here, p is not NULL if(*(p+1) == ‘*‘) { //case 1: *p matches 0 chars in s if(isMatch(s, p+2)) return true; //case 2: try all the possible number of chars that *p matches in s while(matchFirst(s, p)) { s ++; if(isMatch(s, p+2)) return true; } } else { if(matchFirst(s, p)) return isMatch(s+1, p+1); else return false; } } bool matchFirst(const char *s, const char *p) {//match the first char if((*p==*s) || (*p==‘.‘ && *s != 0)) return true; else return false; }};
【LeetCode】Regular Expression Matching
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。