【剑指offer】正则表达式匹配

本题知识点：字符串

题目描述

思路：采用递归的方法。
1. 只有当str和pattern同时为''时，才算成功。
2. 当*str == *pattern 或者 *pattern == '.' && *str != '' 时，我们就认为当前str和pattern是匹配的。
3. 每一轮，我们首先应该考虑pattern+1是不是'*'，接着才是考虑当前str和pattern是否匹配，如果pattern+1是'*'：
3.1. 如果当前str和pattern匹配，此时'*'的作用可能还没有结束，还要考虑以下两种情况（任何一种情况成功都行，所以它们是'或'的关系）：
3.1.1： 匹配str+1和pattern（如果这种情况匹配成功，说明这个'*'前面的字符可能要重复两次以上）
3.1.2： 或者匹配str和pattern+2（如果这种情况匹配成功，说明这个'*'前面的字符需要被忽略）
3.2. 如果当前str和pattern不匹配，那么我们还有机会，忽略当前pattern和pattern+1，接着匹配当前str和pattern+2；
4. 如果pattern+1不是'*'，就正常考虑当前str和pattern是否匹配。
5. 如果3和4都不能返回true，那就只能返回false咯

class Solution {  
public:  
    bool match(char* str,char* pattern)//程序入口  
    {  
        if(str == NULL || pattern == NULL)  
            return false;  
          
        return kernel(str,pattern);   
    }  
      
    bool kernel(char* str,char* pattern)  
    {  
        if(*str == '' && *pattern == '')  
            return true;  
          
        if(*(pattern+1) == '*')  
        {  
            if(*pattern == *str || (*pattern == '.' && *str != ''))//如果当前str和pattern匹配  
                return kernel(str+1,pattern)||kernel(str,pattern+2);//两者任何一个匹配成功都行  
            else  
                return kernel(str,pattern+2);  
        }  
        if(*str == *pattern || (*pattern == '.' && *str != ''))  
            return kernel(str+1,pattern+1);  
  
        return false;  
    }  
};