首页 > 代码库 > [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 正则表达式匹配