10. 正则表达式匹配

发表于 更新于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 1 分钟

题目描述

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

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素。所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。
1
2
3
4
5
示例 4：

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

题解

解析

使用动态规划的方法进行解题，分为两种情况：首先是非*的情况，这种情况下我们需要考虑s和p当前字符是否匹配，很容易得出状态转移方程。然后是p为*，也可以分为两种情况，一种是s的当前字符与p的前一个字符不匹配，那么*就匹配一个字符，另一种是s的当前字符可以和p的前一个字符进行匹配，说明*可以匹配多个字符，两种情况

  • 匹配 s 末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配；
  • 不匹配字符，将该组合扔掉，不再进行匹配。
image-20220227143444739 
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
bool charMatch(char s, char p) {
    if (p == '.' || s == p) return true;
    return false;
}

/* 使用方法：动态规划 */
bool isMatch(char * s, char * p){
    int height = strlen(s);
    int width = strlen(p);
    bool** table = (bool**)malloc(sizeof(bool*) * (height+1));
    if (table == NULL) { printf("Error\n"); return false; }
    for (int i = 0; i <= height; i++) {
        table[i] = (bool*)malloc(sizeof(bool) * (width+1));
        if (table[i] == NULL) { printf("Error\n"); return false; }
    }
    table[0][0] = true;
    for (int i = 1; i <= height; i++) table[i][0] = false;
    for (int i = 1; i <= width; i++) {
        if (p[i-1] == '*' && i >= 2) table[0][i] = table[0][i-2];
        else table[0][i] = false;
    }
    for (int i = 1; i <= height; i++) {
        for (int j = 1; j <= width; j++) {
            if (j >= 2 && p[j-1] == '*' ) {
                if (charMatch(s[i-1], p[j-2]))
                    table[i][j] = table[i-1][j] || table[i][j-2];
                else table[i][j] = table[i][j-2];
            } else if (charMatch(s[i-1], p[j-1])) {
                table[i][j] = table[i-1][j-1];
            } else {
                table[i][j] = false;
            }
        }
    }
    return table[height][width];
}

来源：LeetCode-10