10. 正则表达式匹配&44. 通配符匹配

10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

 
示例 1：

输入：s = “aa”, p = “a”
输出：false
解释：”a” 无法匹配 “aa” 整个字符串。
示例 2:

输入：s = “aa”, p = “a*”
输出：true
解释：因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3：

输入：s = “ab”, p = “.“
输出：true
解释：”.“ 表示可匹配零个或多个（’*’）任意字符（’.’）

---

动态规划

dp[i][j]表示s的前i个字符和p的前j个字符是否匹配。
若p[j-1] != ‘‘, 则看对应字符是否相等；
若p[j-1] == ‘‘, 则需要考虑2种情况：

• p[j-2] == s[i-1], 也就是*前一个字符是否和s对应字符匹配，若匹配则可以匹配1次或多次。其中匹配1次，可以被多次+0次合并。
• p[j-2] != s[i-2], 不匹配，则只能表示匹配0次，消去前一个字符，再比较。

class Solution {
public:
    bool isMatch(string s, string p) {

        // 判断s中第i个字符和p中第j个字符是否匹配
        auto matches = [&](int i, int j) {
            // s的第0个字符不存在，s为空字符串，j不为空，肯定无法匹配
            if (i == 0) return false;
            if (p[j-1] == '.') return true;
            return s[i-1] == p[j-1];
        };

        int m = s.size();
        int n = p.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        dp[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j-1] == '*') {
                    // 若p[j-2]与s[i-1]不等，可考虑将p[j-2]去掉
                    dp[i][j] |= dp[i][j-2];
                    // 若相等，则可以用*替换多次
                    if (matches(i, j-1)) {
                        dp[i][j] |= dp[i-1][j];
                    }
                }else {
                    if (matches(i, j)) {
                        dp[i][j] |= dp[i-1][j-1];
                    }
                }
            }
        }
        return dp[m][n];
    }
};

44. 通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:

输入:
s = “aa”
p = ““
输出: true
解释: ‘‘ 可以匹配任意字符串。
示例 3:

输入:
s = “cb”
p = “?a”
输出: false
解释: ‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。
示例 4:

输入:
s = “adceb”
p = “ab”
输出: true
解释: 第一个 ‘‘ 可以匹配空字符串, 第二个 ‘‘ 可以匹配字符串 “dce”.
示例 5:

输入:
s = “acdcb”
p = “a*c?b”
输出: false

---

动态规划

dp[i][j]表示s的前i个字符和p的前j个字符是否匹配。

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();

        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        // 均为空串时为true
        dp[0][0] = 1;
        // s为空串时，*只能匹配空串，所以只有p为任意个*时才为true
        for (int j = 1; j <= n; j++) {
            if (p[j-1] == '*'){
                dp[0][j] = true;
            }else{
                break;
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j-1] == '*') {
                    // *可以匹配s中的一个字符，也可以不匹配(空串)
                    dp[i][j] = dp[i-1][j] | dp[i][j-1];
                }else {
                    // p为万能符号？或二者对应字符相等
                    if (p[j-1] == '?' || p[j-1] == s[i-1]) {
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
            }
        }
        return dp[m][n];

    }
};