跳转至

Problem 10 - Regular Expression Matching - 正则表达式匹配

2022.01.19

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

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。

输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

动态规划

状态：

f[i][j] 表示 s 的前 i 个 字符与 p 的前 j 个字符能否匹配。

状态转移：

考虑 p[j] 是否等于这个能匹配任意多字符的 *。

若 p[j] != '*'，则只能在 s 中匹配一个字符。那么，当 match(s[i], p[j]) == true 时，f[i][j] 可以由 f[i - 1][j - 1] 转移过来；若不成立，则没有这条转移关系。

若 p[j] == '*'，则我们实际上只有两种情况：

  1. 当 s[i] 可以和 p[i - 1] p[i] 这个整体匹配时，匹配 s[i]，这时 f[i][j] 可以由 f[i - 1][j] 转移；
  2. 不匹配 s[i]，这时相当于直接把 p[j - 1] 和 p[j] 丢掉，f[i][j] 可以由 f[i][j - 2] 转移。

初始值：

f[0][0] = true，同时要记得初始 f[0][j]。

class Solution {
public:
    bool isMatch(string s, string p) {
        s = " " + s;
        p = " " + p;
        static bool f[21][31];
        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int j = 1; j < p.length(); j++) {
            if (p[j] == '*') 
                f[0][j] |= f[0][j - 2];
        }
        for (int i = 1; i < s.length(); i++) {
            for (int j = 1; j < p.length(); j++) {
                if (p[j] != '*' ) {
                    if (s[i] == p[j] || p[j] == '.')
                        f[i][j] |= f[i - 1][j - 1];
                }
                else {
                    if (s[i] == p[j - 1] || p[j - 1] == '.') {
                        f[i][j] |= f[i - 1][j];
                        f[i][j] |= f[i][j - 2];
                    }
                    else f[i][j] |= f[i][j - 2];
                }
                // cout << "f[" << i << "][" << j << "] = " << f[i][j] << endl;
            }
        }
        return f[s.length() - 1][p.length() - 1];
    }
};

DFS

搜索过程中，枚举 * 可以匹配多少个字符即可。

评论