剑指offer 正则表达式匹配

正则表达式匹配

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

解题代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        return MyMath(str, 0, pattern, 0);
    }
    
    //用i，j来表示下标更好的判断是否越界
    bool MyMath(string str,int i,string patten,int j){
        //如果str遍历完成，patten也正好遍历完成的话，说明匹配成功
        if(i>=str.size() && j==patten.size()){
            return true;
        }
        //如果str没有遍历完成，但是patten遍历完成的话，说明匹配失败
        if(i<str.size() && j>=patten.size()){
            return false;
        }
        
        //patten后缀为*
        if(patten[j+1]=='*' && (j+1)<patten.size()){
            //str和patten匹配成功的话
            if(i<str.size() && (str[i]==patten[j] || patten[j]=='.')){
                return (MyMath(str, i+1, patten, j) || MyMath(str, i, patten, j+2));
             }else{
                return MyMath(str, i, patten, j+2);
            }
        }
        
        if((str[i]==patten[j] || patten[j]=='.') && i<str.size()){
            return MyMath(str, i+1, patten, j+1);
        }
        return false;
        
    }
};