AcWing 30. 正则表达式匹配
宋标 Lv5
  2022-08-18 02:31:39 2022-08-18 02:31    

题目

请实现一个函数用来匹配包括'.'和'*'的正则表达式。

模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。

例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。

数据范围

输入字符串长度 。

样例

输入：

s="aa"
p="a*"

输出:true

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:

    vector<vector<int>> f; // f[i][j]表示s串中i下标到结尾与p串中j下标到结尾是否相匹配
    int n, m;

    bool isMatch(string s, string p) {
        n = s.size(); m = p.size();
        f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
        return dp(0, 0, s, p);
    }

    bool dp(int x, int y, string &s, string &p)
    {
        if (f[x][y] != -1) return f[x][y];
        if (y == m)
            return f[x][y] = x == n;
        bool first_match = x < n && (s[x] == p[y] || p[y] == '.');
        bool ans;
        if (y + 1 < m && p[y + 1] == '*')
            ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
        else
            ans = first_match && dp(x + 1, y + 1, s, p);
        return f[x][y] = ans;
    }
};
 评论