leetcode10.正则表达式匹配

Posted on | In |
Words count in article: 328 | Reading time ≈ 1

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

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

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

示例：

1
2
3
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

分析：

img

代码

  • C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        s = " " + s, p = " " + p;
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1, false));
        f[0][0] = true;
        for (int i = 0;i <= n;i ++)
            for (int j = 1;j <= m;j ++) {
                if (j + 1 <= m && p[j + 1] == '*') continue; // 讨论时*与其前面的字符为一个整体
                if (i && p[j] != '*') {
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.'); // 平凡转移
                } else if (p[j] == '*') {
                    // f[i][j - 2]表示丢弃*及其前面字符
                    // f[i - 1][j]表示利用*
                    f[i][j] = f[i][j - 2] || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
                }
            }


        return f[n][m];
    }

};

[原题链接](10. 正则表达式匹配 - 力扣（Leetcode）)

0%