题目描述

题目 : 请实现一个函数用来匹配包括.和*的正则表达式。模式中的字符.表示任意一个字符，而*表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。

输入字符串为str，模式为pattern

解题思路

一看就知道用递归进行求解，主要是如何把情况分析的清楚，让代码不混乱。

主要可以将'*'表示的含义分为三类，当前字符出现0次，1次，1次以上。

根据pattern的第二个字符是不是'*'字符，将情况分为两类。

• pattern的下一个字符为'*'字符，即*(pattern+1)=='*'，此时又分为两种情况：
  1. 如果当前字符匹配，即 *str==*pattern或者*str=='.' && *pattern!='\0'，根据'*'表示的含义划分为三种：
     1. 当前字符出现0次：等价于判断str和pattern+2是否匹配。
     2. 当前字符出现1次：等价于判断str+1和pattern+2是否匹配。
     3. 当前字符出现1次以上：等价于判断str+1和pattern是否匹配。
  2. 如果当前字符不匹配，此时'*'只能表示当前字符出现0次。等价于判断str和pattern+2是否匹配。
• pattern的下一个字符不为'*'字符，即*(pattern+1)!='*'，这时逻辑比较简单：
  1. 如果当前字符匹配，即 *str==*pattern或者*str=='.' && *pattern!='\0'，此时等价于判断str+1和pattern+1是否匹配。
  2. 如果当前字符不匹配，直接返回false即可。

递归停止条件

• 当str和pattern同时为结束字符'\0'的时候，说明可以匹配，返回true。
• 当str还没有遍历结束，但是pattern已经结束的时候，说明已经不可能匹配了，可以直接返回false。

几个例子

• str="", pattern=".*"
• str="aaa", pattern="a*a"
• str="aaa", pattern="ab*a"
• str="aaa", pattern="ab*ac*a

代码

class Solution {  
public:  
    bool match(char* str, char* pattern)  
    {   
        return help(str, pattern);  
    }  
    //主要的递归函数
    bool help( char* str, char* pattern )  
    {  
        if( *str == '\0' && *pattern == '\0' )  
            return true;  
        if( *pattern == '\0' )  
            return false;  
          
        if( *(pattern+1) == '*' )  
        {  
            if( *str == *pattern || (*pattern == '.' && *str != '\0') )  
                return help(str, pattern+2) || help(str+1, pattern+2) || help(str+1, pattern);  
            else  
                return help(str, pattern+2);  
        }  
          
        if( *str == *pattern || (*pattern == '.' && *str != '\0') ) 
            return help(str+1, pattern+1);  
          
        return false;  
    }  
};  

参考

牛客网剑指Offer——正则表达式匹配