解法一：动态规划

与此题类似，此题可以采用动态规划的方法来求解。定义二维递推数组dp，其中表示字符串str的前个字符与字符串pattern的前个字符是否匹配（设dp数组行、列分别为、，其中分别为字符串str和pattern的长度）。

「动态规划算法的关键是确定递推式」，对于此题有如下几种情况：（为方便递推式的表示，dp数组行、列分别为、，故对于字符串str和pattern的索引需要减1）

具体事例如图所示。

1. 当为或时，说明str的第个位置和pattern的第个位置是可以匹配的，因此此时两个字符串是否匹配取决于上个位置，故有;

2. 当为星号时，由于星号可以匹配多次（包括零次）其前一字符，因此需要分如下几种情况讨论：

   1. 当星号匹配零次时，即（星号前一个字符）并不需要用来被匹配，因此此时的匹配情况取决于dp数组在的匹配情况，即：此时;

   2. 当星号匹配一次时，即 （星号前一个字符）用来被匹配，则此时;

   3. 当星号匹配多个字符时，由于 （星号前一个字符）被用来匹配多次，故当前的匹配情况取决于str当前字符（位置）与是否相等（或为一个点）、以及dp数组在前一位置的匹配情况，即;

上述几种情况满足其一则说明当前是匹配成功的，故上述几种情况之间是「或」的关系。

经过上述递推关系，在遍历完两个字符串后，$$即为答案。

根据上述思路，实现的代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        if (pattern.empty()) 
            return str.empty(); 
        int m = str.size(), n = pattern.size();
        vector<vector<bool> > dp(m + 1, vector<bool>(n + 1)); // 定义动态规划数组
        // 初始化
        dp[0][0] = true; 
        for (int i = 2; i <= n; i += 2) {
            if (pattern[i - 1] == '*') 
                dp[0][i] = dp[0][i - 2]; 
        }
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.') // pattern字符串当前字符与str字符串当前字符相等，或pattern字符串当前字符为`.`
                    dp[i][j] = dp[i - 1][j - 1]; 
                else if (pattern[j - 1] == '*') { // pattern字符串当前字符为`*`
                    if (dp[i][j - 1]) { // 星号匹配一次
                        dp[i][j] = dp[i][j - 1]; 
                    }
                    else if (j >= 2 && dp[i][j - 2]) { // 星号匹配零次
                        dp[i][j] = dp[i][j - 2]; 
                    }
                    else if (i >= 2 && j >= 2) // 星号匹配多次
                        dp[i][j] = (dp[i - 1][j] && (str[i - 1] == pattern[j - 2] || pattern[j - 2] == '.'));  
                }
            }
        }
        return dp[m][n]; 
    }
};

该方法需要两层循环分别遍历两个字符串，故算法时间复杂度为，其中分别为str字符串和pattern字符串的长度；该方法需要定义大小为的dp数组，故空间复杂度为。

解法二：递归解法

此题亦可以采用「递归」的方法实现，具体思路如下：

1. 定义递归函数，该函数分别将「两个字符串当前需要匹配的位置」作为参数传入，并分情况考虑「pattern字符串下一位置」的元素情况（设字符串str、pattern当前匹配的位置分别为；函数原型为）：

   1. 当为一个数字或为一个点时，此时判断「当前位置两个字符串是否匹配」，若不匹配，则直接返回，否则继续判断下一位置：;

   2. 当为星号时，与解法一思路相同，此处需要分情况讨论：

      • 在当前位置str字符串和pattern字符串不匹配，则直接考虑星号后面一个位置的匹配情况，即下一次递归为：;

      • 否则：

        1. 当星号匹配零个字符时，说明和都未被用到，因此，此时pattern字符串的下一个位置应该要跳过星号，而str字符串匹配位置不变（因为当前位置未匹配字符），因此下一层递归为：;

        2. 当星号匹配一个字符时，说明被用到了，因此下一层递归为：;

        3. 当星号匹配多个字符时，说明在下一层递归时也仍会被用来匹配，因此下一层递归为：;

2. 递归的终止条件为：

   1. 两个字符串都匹配到结尾，说明匹配成功；
   2. str字符串未匹配完，但pattern字符串已经被匹配完了，说明匹配失败。

基于上述思路，实现的代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        if (str.size() && pattern.empty()) 
            return false; 
        return helper(str, pattern, 0, 0); 
    }
    bool helper(string str, string pattern, int i, int j) {
        if (i >= str.size() && j >= pattern.size()) // 两个字符串都匹配完
            return true; 
        if (i < str.size() && j >= pattern.size()) // pattern字符串匹配完了，但str字符串未匹配完
            return false; 
        if ((j < pattern.size() - 1 && pattern[j + 1] != '*') || j + 1 == pattern.size()) { // pattern下一个字符不为星号
            if (i < str.size() && (str[i] == pattern[j] || pattern[j] == '.')) // 当前能够匹配
                return helper(str, pattern, i + 1, j + 1); // 下一层递归
            else return false; // 当前位置匹配失败，返回false
        }
        // pattern下一个位置为星号
        if (i < str.size() && str[i] != pattern[j] && pattern[j] != '.' || i == str.size()) // 当前位置不能成功匹配，说明pattern[j]字符不能被使用
            return helper(str, pattern, i, j + 2); 
        return helper(str, pattern, i, j + 2) || helper(str, pattern, i + 1, j + 2) || helper(str, pattern, i + 1, j); // 当前位置成功匹配，分为星号匹配0次、1次、多次三种情况
    }
};

考虑此方法的时间复杂度：在递归函数的最后一个语句，若从开始分析，则构建的递归树示意图如下（假设在最坏情况下，最后的中的三个「或」语句都被调用了）：

若将看做二维空间中的每个点，则整个递归树在最坏情况下可以遍历到从到的所有点的（其中分别为str字符串和pattern字符串的长度），故时间复杂度为，也即树的结点个数；递归的空间复杂度是由函数栈空间的层数确定的（因为函数在「每一层」递归空间复杂度为），由于递归过程在「字符串到达末尾」时便终止，故空间复杂度为，也就是树的高度。