leetcode10--正则表达式

1. 题意

写一个支持$.\ast$的正则式匹配

2. 题解

主要是状态转移方程
d p [ i ] [ j ] = { d p [ i − 1 ] [ j − 1 ] & s [ i ] = p [ j ] p [ j ] ≠ ∗ d p [ i − 1 ] [ j ] & p [ j − 1 ] = s [ i ]   ∣   d p [ i ] [ j − 2 ] p [ j ] = ∗ dp[i][j]=

dp[i][j]={dp[i−1][j−1]&s[i]=p[j]p[j]=∗dp[i−1][j]&p[j−1]=s[i] ∣ dp[i][j−2]p[j]=∗​

官方解

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

        auto matches = [&](int i, int j) {
            if (i == 0) {
                return false;
            }
            if (p[j - 1] == '.') {
                return true;
            }
            return s[i - 1] == p[j - 1];
        };

        vector<vector<int>> f(m + 1, vector<int>(n + 1));
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i][j] |= f[i][j - 2];
                    if (matches(i, j - 1)) {
                        f[i][j] |= f[i - 1][j];
                    }
                }
                else {
                    if (matches(i, j)) {
                        f[i][j] |= f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }
};

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
27
28
29
30
31
32
33
34
35
36
37