LeetCode:10.正则表达式匹配；44. 通配符匹配；

10.正则表达式的匹配 注释程序去解答题目，递归

class Solution {
          
   
public:
    bool isMatch(string s, string p) {
          
   
        return matchCore((char*)s.c_str(),(char*)p.c_str());
    }
    bool matchCore(char *str,char * pat){
          
   
        if(*str== && *pat==)  //str同时为空
            return true;
        if(*str!= && *pat==)
            return false;
        if(*(pat+1)==*){
          
   //如果后面是*的话怎么办
            if(*pat==*str || (*pat==. && *str!=)){
          
   
                //     abc---->a*bc 星号隔过去     aaaabc---->a*bc利用星号的下一次重复   a---->a*a  将本次隔过去
                return matchCore(str+1,pat+2) || matchCore(str+1,pat) || matchCore(str,pat+2);
            }else{
          
   
                //     abc---->d*bc  将本次隔过去
                return matchCore(str,pat+2);
            }
        }
        //这个没有疑问直接往后移动就可以了 abc-->abc   abc--->.bc
        if(*str==*pat || (*pat==. && *str!=))
            return matchCore(str+1,pat+1);
        return false;
    }
};

44. 通配符匹配；

class Solution {
          
   
    //动态规划
    //m[i][j]表示s(0 ~ i-1)和 p(0 ~ j-1)是否匹配
public:
    bool isMatch(string s, string p) {
          
   
        vector<vector<bool>> m(s.size()+1,vector<bool>(p.size()+1));
        
        m[0][0] = true; //两个字符串都为空是肯定匹配
        for(int i = 0; i <= s.length(); i++) {
          
   
            for(int j = 1; j <= p.length(); j++) {
          
   
                if(p[j-1] == *) {
          
   
                    //m[i][j-1] 即当前*匹配一个空字符
                    //m[i-1][j] 即当前*匹配一个字符s.charAt(i-1)
                    //这里之所以不是m[i-1][j-1]是因为当前*可能在前面一匹配了若干个字符
                    //         abc,ab[*]
                    m[i][j] = m[i][j-1] || (i > 0 && m[i-1][j]);
                } else {
          
   
                    //前面的m(0~i-2)和p(0~j-2)能匹配且当前字符能匹配
                    //比如abc,abd
                    m[i][j] = i > 0 && m[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == ?);
                }
            }
        }
        return m[s.length()][p.length()];
    }
    
};