首页 > 代码库 > [Leetcode] Regular expression matching 正则表达式匹配
[Leetcode] 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") → 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
题意:‘ . ‘能匹配任意字符,‘ * ‘表示之前的那个字符可以是0个、1个或者多个,(注意:s= ba和 p= a*bc也是匹配的,*表示p中 * 之前的字符为0个,但s=‘bc’和 p=‘aa*bc’是不匹配的)。
思路:根据字符‘ * ‘的特殊性,整体的解决方法主要是分两种情况:
一、p的第二个字符*(p+1)不是 ‘ * ‘,这种情况,只要存在 *s==*p 或者*p=‘ . ‘中的一种情况,就说明当前p 和 s 对应的字符匹配,就可以比较两个的下一个字符(这有一个前提,就是 s 要不为空,要是 s 为空了,就不匹配了,不用继续比较了);
二、p的第二个字符*(p+1)是 ‘ * ‘,这种情况就比较麻烦了,也分两种情况:
1) 在*s==*p 或者*p==‘ . ‘其中的一种情况下,判断 ‘ * ‘是代表0个、1个或者多个前一个字符,如何去实现了?先将 *s 和*(p+2)去匹配,看是否能匹配,若能代表*表示0个之前字符,若是不能,则将s++,然后和P接着匹配,看是否匹配,若是,则将 *s 和*(p+2)去匹配继续上部分的循环;若不是,则直接将 *s 和*(p+2)去匹配,不用继续判断*s和*p是否匹配。是有点绕口,结合代码看,可能稍微好些。如:s= aba和 p= a*ba或者s= aab和 p= a*bc
2)*s !=*p 和*p !=‘ . ‘,说明,p中的第一个字符,在s中不存在,直接说明 ‘ * ‘代表0个之前的字符,那么就继续判断 *s 和*(p+2)是否匹配。如s= ba和 p= a*bc是匹配,s= ba和 p= a*cbc则是不匹配,但是说明依旧说明在开始判断时,‘ * ‘代表0个 a。
结合 : 当p为空,若s也为空,返回true,反之返回false; 当p的长度为1,若s长度也为1,且相同或是p为‘.‘则返回true,反之返回false;代码如下:
1 class Solution { 2 public: 3 bool isMatch(const char *s, const char *p) 4 { 5 if(*p==‘\0‘) return *s==‘\0‘; 6 if(*(p+1) ==‘*‘) 7 { 8 while(*p==*s||(*p==‘.‘&&*s !=‘\0‘)) 9 { 10 if(isMatch(s++,p+2)) //判断*之前元素的个数 11 return true; 12 } 13 return isMatch(s,p+2); //直接匹配字符*的下一个 14 } 15 else 16 { 17 if(*p==*s||(*p==‘.‘&&*s !=‘\0‘)) 18 return isMatch(s+1,p+1); 19 return false; 20 } 21 } 22 };
还有一种利用动态规划的方法,暂时没有看太懂,这里给出链接1 ,链接2,方便以后揣摩。
[Leetcode] Regular expression matching 正则表达式匹配