方法一：递归

1.解题思路

题意：
给定一个文本串和一个模式串，模式串中字符' . '表示任意一个字符，模式串中的' * '表示任意次' * '前字符，让我们判断文本串与模式串是否匹配,匹配返回true，不匹配返回false。

2.解法

采用递归方法，首先进行特判。

• 空文本串，空模式串，一定匹配
• 文本串，空模式串，一定不匹配

然后在文本串不空的条件下不断顺序判断文本串和模式串的第一个字符元素是否匹配，并用一个bool变量记录。
接着将前面的字符去掉，用substr(开始位置，截取长度)截取剩余的字符，不断递归下去。

• 模式串下一个元素是' * '时，可直接从模式串下一个位开始比较（即模式串中' * '及前一个字符在文本串对应位置找不到，' * '及前一个字符就直接舍去），或在当前位匹配的前提下匹配下一位文本串（即模式串中' * '及前一个字符在文本串对应位置能找到，文本串顺移接着匹配模式串）。
• 模式串下一个元素是' . '或普通字符时，在上一次两串匹配的前提下，进入文本串与模式串的各下一位的匹配。

3.具体代码

class Solution {
public:
    bool match(string str, string pattern) {
        if (pattern.empty()) return str.empty();//
        bool now_match = !str.empty() && (pattern[0] == str[0] || pattern[0] == '.');//第一个元素匹配 
        if (pattern.length()>=2 && pattern[1]=='*')//当前元素是* 
            return match(str, pattern.substr(2, pattern.length()))||(now_match && match(str.substr(1, str.length()), pattern));//now_match判断当前是否匹配，可直接从模式串下一个位开始比较，或在当前位匹配的前提下匹配下一位模式串 
        else //当前元素是.或正常字符 
            return now_match && match(str.substr(1, str.length()), pattern.substr(1, pattern.length()));//now_match判断当前是否匹配，匹配进入文本串与模式串的各下一位的匹配 
    }
};

4.时间复杂度和空间复杂度分析

时间复杂度:，m和n分别是文本串和模式串的长度，遍历两串
空间复杂度:，m和n分别是文本串和模式串的长度，递归的每层空间复杂度为，递归树最大高度为m+n。

方法二：动态规划

1.解题思路

因为可以想到先比较两串的子串，子串不匹配则两串也不匹配，子串匹配则扩大子串范围直至两串比较。

开始比较文本串与模式串，动态规划采用自底向上方法计算出最优值，即文本串当前位是否匹配模式串当前位取决于之前子串的比较结果。

2.解法

设立表示文本串的前i个字符与模式串的前j个字符是否匹配。

• 初始化，分别讨论文本串，模式串是否为空，可分为以下四类。
  • 空文本串，空模式串，一定匹配，；
  • 文本串，空模式串，一定不匹配，;
  • 空文本串，模式串，需计算
  • 文本串，模式串，需计算
• 计算，倒着比较模式串文本串
  • 若模式串当前位是普通字符，直接比较文本串与模式串该位，匹配的情况下取决于两串该位之前字符匹配，。
  • 若模式串当前位是'.'，说明文本串与模式串该位一定匹配，取决于两串该位之前字符匹配，。
  • 若模式串当前位是''，因为''要结合它前面一位进行匹配。
    • 若'*'表示前一位字符出现0次，则直接舍去模式串的这两位，接着拿文本串当前位比较模式串的这两位前的一个字符，。
    • 若''表示前一位字符出现多次，则在模式串''前字符与文本串当前位比较相等的情况下（出现一次，比较一次），不断比较模式串'*'前字符与文本串上一次比较的前一位，。
• 转移方程
  • ，模式串当前位是普通字符且两串对应位相匹配，或模式串当前位是'.'
  • ，模式串当前位是''且''前字符与文本串当前位不匹配
  • ，模式串当前位是''且''前字符与文本串当前位匹配

3.图解

4.具体代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        int n=str.size(),m=pattern.size();
        vector<vector<bool> >dp(n+1,vector<bool>(m+1,false));//二维数组dp[i][j],表示文本串前i个与模式串前j个是否匹配
        dp[0][0]=1;//空文本串与空模式串一定匹配 
        for(int i=1;i<=n;i++){
            dp[i][0]=0;//非空文本串与空模式串一定不匹配     
        }        
        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                if(!j)continue;
                if(pattern[j-1]!='*'){//对应位是正常字符或. 
                    if(i>0&&(str[i-1]==pattern[j-1]||pattern[j-1]=='.'))dp[i][j]=dp[i-1][j-1];//匹配则接着对分别比下一位 
                }else{//对应位是* 
                    if(j>=2)dp[i][j]=dp[i][j]||dp[i][j-2];//文本串最后字符与模式串最后两个字符不匹配，则不管模式串最后两个字符            
                    if(i>=1&&j>=2&&str[i-1]==pattern[j-2]||pattern[j-2]=='.')dp[i][j]=dp[i][j]||dp[i-1][j];//匹配则接着对比文本串下一位 
                }
            } 
        } 
        return dp[n][m]; 
    }
};

5.时间复杂度和空间复杂度分析

时间复杂度：，m和n分别是文本串和模式串的长度，遍历整个dp数组。
空间复杂度：，m和n分别是文本串和模式串的长度，使用到了二维数组dp。