首页 > 代码库 > 52、剑指offer--正则表达式匹配

52、剑指offer--正则表达式匹配

题目描述
请实现一个函数用来匹配包括‘.‘和‘*‘的正则表达式。模式中的字符‘.‘表示任意一个字符,而‘*‘表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配
 
思路:只有当模式串和字符串同时等于\0,才可以认为两个串匹配。
           如果第二个字符不是*比较简单,则第一个字符相匹配那么字符和模式都向后移1,匹配剩下的,否则返回false      
       在匹配中,如果第二个字符是*比较复杂。对于每个位的匹配可以分为三种情况
           1、(相应位匹配||模式串为.&&字符串不是\0)&&模式串下一位是*
           2、(相应位匹配||模式串为.&&字符串不是\0)&&模式串下一位不是*
           3、相应位不匹配&&(模式位不为.||字符串是\0)对应1,最复杂。
           分为*取0,*取1,*>=2三种情况。
           *取0对应跳过当前匹配位,继续寻找patter的下一个匹配位,str不变,pattern+2
           *取1对应当前匹配位算一次成功匹配,str+1,pattern+2
           *取>=2对应一次成功匹配,继续匹配字符串的下一位是否匹配,str+1,pattern不变三者取或。
            即只要有一种情况能匹配成功认为字符串就是匹配成功的。
            对应2,相当于一次成功匹配,str+1,pattern+1
            对应3,匹配失败,直接返回false
 1 class Solution {
 2 public:
 3     bool match(char* str, char* pattern)
 4     {
 5         if(str == NULL || pattern == NULL)
 6         {
 7             return false;
 8         }
 9         return matchCore(str,pattern);
10     }
11     bool matchCore(char *str, char *pattern)
12     {
13         if(*str == \0 && *pattern == \0)
14             return true;
15         if(*str != \0 && *pattern == \0)
16             return false;
17         if(*(pattern+1) == *)//下一位为*(注意优先级问题加())
18         {
19             if(*pattern == *str || (*pattern == . && *str != \0))//当前位匹配
20             {
21                 return matchCore(str+1,pattern+2)//匹配一个
22                     || matchCore(str+1,pattern)//匹配>=2个
23                     || matchCore(str,pattern+2);//匹配0个
24             }
25             else
26             {
27                 return matchCore(str,pattern+2);//匹配0个
28             }
29         }
30         if(*str == *pattern ||(*pattern == . && *str !=\0))
31             return matchCore(str+1,pattern+1);
32         return false;
33     }
34 };

 

52、剑指offer--正则表达式匹配