LeetCode10 正则表达式匹配

发表于 | 分类于 |
字数统计: 621 | 阅读时长 ≈ 2

链接：https://leetcode-cn.com/problems/regular-expression-matching/description/

题面

给你一个字符串 s 和一个正则表达式 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。求该字符串是否可以被匹配

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

    解法

    设立状态dp[i][j]表示s的前i个字符和p的前j个字符是否可以匹配
    首先进行初始化，对于dp[0][j]如果第j个字符时*的话，有可能符合0字符的情况，初始化为1
    考虑状态转移方式，有以下几种情况
  1. p[j]是’.’ 即可以匹配任意字符 这种情况下只需要考虑s和p之前的字符串是否可以匹配 $ dp[i][j] = dp[i - 1][j - 1] $
  2. p[j]是普通字符，这时只需要考虑s[i - 1]和p[j - 1]是否相同，并且之前的字符串是否可以匹配
  3. p[j]是’*’时存在两种情况
    • p[j - 2] 和 s[i - 1]可以匹配
      这个时候dp[i][j]可以从dp[i][j - 2] (扩充为零字符) dp[i][j - 1] (扩充为1个字符) 以及 dp[i - 1][j] (增加一个字符匹配，只要之前是匹配即可)
      例如abbbbb和ab*，就是不断地从dp[i - 1][j]转移而来的情况
    • p[j - 2] 和 s[i - 1] 无法匹配(两者不同且p[j - 1]不是’.’)
      这个时候只能考虑将*扩充为空

代码

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
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        // dp[i][j]表示以i截止的字符串是否可以被以j截止的正则式匹配
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            if (p[i - 1] == '*') {
                dp[0][i] = dp[0][i - 2];
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else if (p[j - 1] == '*') {
                    if (p[j - 2] != s[i - 1] && p[j - 2] != '.') {
                        // 当前p的字符为* 如果p前一个字符不是.且和s当前字符不同
                        dp[i][j] = dp[i][j - 2];
                    }
                    else {
                        dp[i][j] = dp[i][j - 2] | dp[i][j - 1] | dp[i - 1][j];
                    }
                }
                else {
                    dp[i][j] = dp[i - 1][j - 1] && s[i - 1] == p[j - 1];
                }
            }
        }
        return dp[m][n];

    }
};