题解 | #正则表达式匹配#

方法一：动态规划

创建一个bool类型数组dp，大小为（str.length() + 1）* （pattern.length() + 1），用来存储str到pattern是否匹配；

dp[i][j] 表示str[i - 1]和pattern[j - 1]是否匹配，可以得到如下的状态转移方程：

如果str[i - 1] == pattern[j - 1]或者pattern[j - 1] =='.'(可替代任何字符，等同于相等)，dp[i][j] = dp[i - 1][j - 1]；

如果不相等时，只要当pattern[j - 1]为‘*’时，才有可能匹配，可以分三种情况讨论：

（1）重复0次：dp[i][j] = dp[i][j - 2]；

（2）重复1次：dp[i][j] = dp[i][j - 1]；

（3）重复多次：dp[i][j] = dp[i - 1][j]；

时间复杂度：o(mn)

空间复杂度：o(mn)

class Solution {
public:
    bool match(string str, string pattern) {
        vector<vector<bool> > dp(str.length() + 1, vector<bool>(pattern.length() + 1, false));
        // 边界设置
        dp[0][0] = true;
        for (int i = 1; i <= pattern.length(); i++) {
            if (pattern[i - 1] == '*')
                dp[0][i] = dp[0][i - 2];
        }

        for (int i = 1; i <= str.length(); i++) {
            for (int j = 1; j <= pattern.length(); j++) {
                if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pattern[j - 1] == '*') {
                    // 重复0次
                    if (dp[i][j - 2] && j >= 2)
                        dp[i][j] = dp[i][j - 2];
                    // 重复1次
                    else if (dp[i][j - 1] && j >= 1)
                        dp[i][j] = dp[i][j - 1];
                    // 重复多次
                    else if ((str[i - 1] == pattern[j - 2] || pattern[j - 2] == '.') && 
                            j >= 2 && i >= 1) {
                                dp[i][j] = dp[i - 1][j];
                            }
                }
            }
        }
        return dp[str.length()][pattern.length()];
    }
};

方法二：递归

此方法复杂度较高，会导致超时。

class Solution {
  public:
    bool match(string str, string pattern) {
        return matchCore(str, pattern);
    }

    bool matchCore(string str, string pattern) {
        if (str.empty() && pattern.empty())
            return true;
        if (!str.empty() && pattern.empty())
            return false;

        if (pattern[1] == '*') {
            if (pattern[0] == str[0] || (pattern[0] == '.' && !str.empty()))
                // 重复0次
                return matchCore(str, pattern.substr(2)) ||
                       // 重复一次
                       matchCore(str.substr(1), pattern.substr(2)) ||
                       // 重复多次
                       matchCore(str.substr(1), pattern);
            else
                return matchCore(str, pattern.substr(2));
        }
        if (str[0] == pattern[0] || (pattern[0] == '.' && !str.empty()))
            return matchCore(str.substr(1), pattern.substr(1));

        return false;
    }
};