题目描述

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

算法思路:引自Maokt 每次从字符串里取出一个字符与模式中的字符匹配，如果模式中的字符是‘.’，它可以匹配字符串中的任意字符，如果不是，那么如果它与字符串中的字符相等则匹配。当字符串的字符和模式的字符匹配时，接着匹配后面的字符。
下面，考虑模式中的第二个字符是不是‘* ’。如果不是，则可以分为两种情况：

1、如果字符串中的第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的字符串和模式；
2、如果字符串中的第一个字符和模式中的第一个字符不匹配，则直接返回false。 当模式中的第二个字符是‘* ’时，又可以分为两种情况方式：
1、如果pattern中的第一个字符和str中的第一个字符不匹配，则将pattern后移两个字符，相当于忽略‘’和它前面的字符，因为‘’可以匹配字符串中的0个字符；
2、如果pattern中的第一个字符和str中的第一个字符匹配，则str后移一个字符，而在模式上又有两种选择：
2.1、pattern后移两个字符（例如字符串"ab"和模式"a* ab"匹配到str[0]和pattern[0]时，pattern后移两个字符，字符串后移一个字符）
2.2、pattern保持不变（例如字符串"aabbba"和模式"aab* a"匹配到str[2]和pattern[2]时，pattern保持不变，字符串后移一个字符）

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool myMatch(string &s, string &p, int i, int j){
        if(i<0&&j<0)
            return true;
        if(j<0)
            return false;
        //匹配一般字符
        if(i>=0&&s[i]==p[j])
            return myMatch(s, p, i-1, j-1);
        //匹配.
        if(i>=0&&p[j]=='.')
            return myMatch(s, p, i-1, j-1);
        //匹配*
        if(p[j]=='*'){
            //匹配0个字符
            if(myMatch(s, p, i, j-2))
                return true;
            //匹配一个字符后递归调用
            if(i>=0&&(p[j-1]=='.'||s[i]==p[j-1]))
                if(myMatch(s, p, i-1, j))
                    return true;
        }
                return false;
    }
    bool match(string str, string pattern) {
        // write code here
        return myMatch(str, pattern, str.size()-1, 											pattern.size()-1);
    }
};