一、递归

一、前提:

1、大问题变小问题

2、找到终止条件

二、如果把大问题变成小问题呢？

当前问题是str字符串和pattern字符串匹配
- 最小的情况是两边都为空, 其次是两边各有1个字符, 再其次是两边都有字符。而以上最小的情况分两类，前两种情况可以作为终止条件,其中若str为空pattern不为空需要进行计算("","a* a* a*"),而最后一种情况可以继续进行递归。
- 接下来需要判断如何递归，如果通过判断pattern当前字符进行划分，那么当前字符是* 号接下来就无从下手了，那我们就需要至少两个字符开始考虑。
  - 如果第2个字符不为星号，那么只需判断str和pattern当前的字符是否匹配，匹配则进行下一个字符匹配，不匹配就return false。
  - 如果第2个字符为星号，我们就可以选择忽略当前的匹配(a,a* a),匹配一次(a,a*),匹配多次(aa,a*),直接看代码就看得懂。

已解决超时问题: "aaaaaaaaaaaaab","aaaaaaaaaac"

 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @param pattern string字符串
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here
        return to_match(str,pattern);
    }
     
    bool to_match(string str,string pattern){
        if(0==str.size()&&0==pattern.size()){
            return true;
        }
        if(str.size()&&pattern.empty()){
            return false;
        }
        if(str.empty()&&2<=pattern.size()&&pattern[1]=='*'){
            return to_match(str,pattern.substr(2));//("","a*a*")
        }
        //下一个是星号
        if(2<=pattern.size()&&pattern[1]=='*'){
            if((pattern[0]==str[0]||pattern[0]=='.')&&!str.empty()){
                return
                  //匹配0次，或说忽略此次的*("a", ".*a")
                  to_match(str,pattern.substr(2))
                  //处理多个字符的(aa,a*)和上一个函数结合就能处理1个字符，比如先执行第二个函数再执行第一个函数
                 || to_match(str.substr(1),pattern);            
              // 如果加上这个只处理1个字符的情况会超时
              //|| to_match(str.substr(1),pattern.substr(2))//(ab,a*b)
            }
            // 有星号，但字符不相等("aab","c*a*b")
            return to_match(str,pattern.substr(2));//
        }
        //没有星号
        if(!str.empty()&&(pattern[0]==str[0]||pattern[0]=='.')){
            return to_match(str.substr(1),pattern.substr(1));
        }
 
        return false;
         
    }
         
};

二、动态规划

1、公式的定义

dp[m][n] 表示str和pattern的匹配情况, dp[0][0] 表示空串空正则, dp[1][1] 表示str第一个字符和pattern第一个字符进行匹配。

dp[m][n] 为最终的匹配结果，为1则匹配成功。

2、初始条件

空串空正则(str="",pattern="")为true

空串非空正则, 需要计算(str="",pattern="a* a* a*")

非空串空正则(str="a",pattern="")为false

非空串非空正则, 需要计算

1、递推公式

1、当前str和(当前pattern匹配||pattern[j]=='.'),则dp[i][j]=dp[i-1][j-1] （即考虑str前i-1个字符和pattern前j-1个字符是否匹配）

2、当前pattern为星号，则需要考虑几种情况，星号前面的字符能匹配几次

如果匹配0次，就是不考虑星号前面字符，即dp[i][j]=dp[i][j-2]
如果匹配1次，就要判断星前字符是否和str当前字符相等，如果相等，则dp[i][j]=dp[i][j-1] (相当于延申了dp[i][j-1],如果是不相等的，dp[i][j-1]也应该为0),这个dp[i][j]不仅可以解决(a,a*)的情况，还为多次匹配打基础了。
如果匹配多次(可以先认为是匹配第二次)，也要判断星前字符是否和str当前字符相等，如果相等，像匹配1次一样，dp[i][j]按道理也是等于dp[i][j-1],但你会发现在(aa,a*)匹配过程中，dp[i][j-1]==0,为什么呢？因为此时的dp[i][j]不是匹配一次的情况，匹配一次才是从左边延申，而匹配第2次的时候，它已经是从匹配了第一次的地方延申，即dp[i-1][j] （当前dp[i][j]的头顶上，即匹配一次时若成功，则* 字符延申过来），结果就是dp[i][j]=dp[i-1][j],相当于判断少1次匹配时是否成功，如果成功，加上当前也相等，则dp[i][j]==1,就匹配成功。


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here
        int m  = str.size(),n = pattern.size();
        if(m!=0&&n==0)return false;
        vector<vector<int> > dp(m+1,vector<int>(n+1,0));
        dp[0][0]=1;
        for(int i=2;i<=n;i+=2){
            dp[0][i]=dp[0][0];//空串，非空正则 ("","a*a*a*")
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(str[i-1]==pattern[j-1]||pattern[j-1]=='.'){
                    dp[i][j]=dp[i-1][j-1];continue;
                }
                //有星的情况
                if(j>2&&pattern[j-1]=='*'){
                    dp[i][j]|=dp[i][j-2];//不匹配当前的
                }
                if(j>=2&&pattern[j-1]=='*'&&(pattern[j-2]==str[i-1]||pattern[j-2]=='.')){
                    dp[i][j]|=dp[i][j-1];//只匹配1次(a*,a)
                }
                if(j>=2&&pattern[j-1]=='*'&&(dp[i-1][j]&&pattern[j-2]==str[i-1]||pattern[j-2]=='.')){
                    dp[i][j]|=dp[i-1][j];//匹配多次(a*,aa)
                }
            }
        }
        
       return dp[m][n];
    }
};