10. 正则表达式匹配

题目链接

解题思路：先写一个暴力递归，bool process(s, p, i, j)，s[i...]与p[j...]能否匹配成功？，i之前，以及j之前的都已经匹配成功了。

• 1️⃣p[j + 1] != '*'

  • 若p[j] == '.'，则递归调用process(s, p, i + 1, j + 1)

  • 若p[j] != s[i]，返回false，否则返回process(s, p, i + 1, j + 1)

• 2️⃣p[j + 1] == '*'

  • 若p[j] == '.'，匹配0个.，即process(s, p, i, j + 2)，匹配多个.，即process(s, p, i + 1, j)，这两个递归，任意一个返回true，则是true
  • 若p[j] == s[i]，匹配0个s[j]，即process(s, p, i, j + 2)，匹配多个s[j]，即process(s, p, i + 1, j)，两个递归，任意一个返回true，则是true，和上面可以合并成一个。
  • 若p[j] != s[i]，只能匹配0个p[j]，即process(s, p, i, j + 2)

有了暴力递归，可以发现，可变参数就是i和j，所以可以加dp缓存表。

代码

class Solution {
public:

    // 现在匹配s[i...]以及p[j...]，之前的已经匹配ok了，dp是缓存表，0表示false，1表示true，-1表示没有计算
    bool process(string &s, string &p, int i, int j, vector<vector<int>> &dp) {
        if (i == s.length() && j == p.length()) {    // 递归终止条件
            return true;
        }
        if (i == s.length()) {    // 递归终止条件
            if (j + 1 ==p.length()) {
                return false;
            }
            if (p[j + 1] == '*') {
                return process(s, p, i, j + 2, dp);
            }
            return false;
        }
        if (j == p.length()) {
            return false;
        }
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        if (j + 1 < p.length()) {
            if (p[j + 1] != '*') {
                if (p[j] == '.') {
                    dp[i][j] = process(s, p, i + 1, j + 1, dp);
                    return dp[i][j];
                } 
                // p[j] != s[i]
                if (p[j] != s[i]) {
                    dp[i][j] = false;
                    return false;
                }
                // p[j] == s[i]
                dp[i][j] = process(s, p, i + 1, j + 1, dp);
                return dp[i][j];
            }
            // p[j + 1] == '*'
            if (p[j] == '.' || p[j] == s[i]) {
                bool next = process(s, p, i, j + 2, dp);    // 匹配0个
                if (next) {    // 如果匹配成功了  就不用往下走了
                    dp[i][j] = true;
                    return true;
                }
                // 匹配多个
                next = process(s, p, i + 1, j, dp);
                dp[i][j] = next;
                return next;
            }
            // p[j] != s[i]
            dp[i][j] = process(s, p, i, j + 2, dp);
            return dp[i][j];
        }
        // j是最后一个字符了
        if (p[j] == '.' || s[i] == p[j]) {
            dp[i][j] = process(s, p, i + 1, j + 1, dp);
            return dp[i][j];
        }
        // s[i] != p[j]
        dp[i][j] = false;
        return false;

    }


    bool isMatch(string s, string p) {
        int n1 = s.length();
        int n2 = p.length();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, -1));
        return process(s, p, 0, 0, dp);
    }
};