LeetCode OJ 之 Regular Expression Matching (正则表达式匹配
发布时间:2020-12-14 01:26:47 所属栏目:百科 来源:网络整理
导读:题目: 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 pro
题目: Implement regular expression matching with support for '.' 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") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa","a*") → true
isMatch("aa",".*") → true
isMatch("ab",".*") → true
isMatch("aab","c*a*b") → true
正则表达式匹配,. 可以匹配任何单个字符。 * 零次或多次匹配前面的字符或子表达式。例如,zo* 可以匹配“z”和“zoo”。前面一个*表示o一次也没有。 思路:当前字符的下一个字符为 * 时,有两种情况,1、* 表示0次前一个字符,则对(s,p+2)递归调用匹配。如 s = abc,p = m*abc 。 2、如果当前字符匹配,则对(s+1,p)递归调用匹配。此时 * 至少表示一次前一个字符。如 s = aaabc,p = a*abc 。 两种情况只要有一个满足即匹配。 代码:class Solution { public: bool isMatch(const char *s,const char *p) { if (*p == ' ') return *s == ' '; // next char is not '*',then must match current character if (*(p + 1) != '*') { if (*p == *s || (*p == '.' && *s != ' ')) return isMatch(s + 1,p + 1); else return false; } else { // next char is '*' return isMatch(s,p + 2) || (*p == *s || (*p == '.' && *s != ' ')) && isMatch(s + 1,p); } } }; 更新: class Solution { public: bool isMatch(string s,string p) { const char *s1 = s.c_str(); const char *s2 = p.c_str(); return isMatch(s1,s2); } bool isMatch(const char *s1,const char *p1) { if(*p1 == ' ') return *s1 == ' '; if(*(p1+1) != '*') { if(*s1 == *p1 || (*p1 == '.' && *s1 != ' ')) return isMatch(s1+1,p1+1); else return false; } else { return isMatch(s1,p1+2) || (*s1 == *p1 || (*p1 == '.' && *s1 != ' ')) && isMatch(s1+1,p1); } } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |