剑指19：正则表达式匹配

传送门

nowcoder
leetcode

题目描述

请实现一个函数用来匹配包括 '.' 和 '*' 的正则表达式。
模式中的字符 '.' 表示任意一个字符，而 '*' 表示它前面的字符可以出现任意次（包含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。
例如：字符串 “aaa” 与模式 “a.a” 和 “abaca” 匹配，但是与 “aa.a” 和 “ab*a” 均不匹配。

C++ 代码 - nowcoder

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
38
/*
    状态表示：
        f[i][j]表示 s[1...i] 和 p[1...j] 是否能匹配
    状态计算：
        p[j] != '*', f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.')
        p[j] == '*', f[i][j] = f[i][j - 2] || f[i - 1][j] && (s[i] == p[j] || p[j] == '.')
            1.星号表示0个字符
                f[i][j] = f[i][j − 2];
            2.星号表示非0个字符
                首先 s 的第 i 个字符必须与星号前的字符匹配，
                同时，s 的前 i−1 个字符与 p 的前 j 个字符也应该是匹配的
                f[i][j] = f[i][j - 2] || (f[i - 1][j] && isMatch(s[i], p[j - 1]));

    时间复杂度：O(nm)
        n 表示 s 的长度，m 表示 p 的长度，总共 nm 个状态，
        状态转移复杂度 O(1)，所以总时间复杂度是 O(nm)
*/
class Solution {
  public:
    bool match(string str, string pattern) {
        int m = str.size(), n = pattern.size();
        str = ' ' + str, pattern = ' ' + pattern;
        vector<vector<bool>> f(m + 1, vector<bool>(n + 1));
        f[0][0] = true;
        for (int i = 0; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (j + 1 <= n && pattern[j + 1] == '*') continue;
                if (i && pattern[j] != '*') {
                    f[i][j] = f[i - 1][j - 1] && (str[i] == pattern[j] || pattern[j] == '.');
                } else if (pattern[j] == '*') {
                    f[i][j] = f[i][j - 2] || i && f[i - 1][j] && 
                        (str[i] == pattern[j - 1] || pattern[j - 1] == '.');
                }
            }
        }
        return f[m][n];
    }
};

C++ 代码 - leetcode

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
38
39
40
41
42
43
44
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        s = ' ' + s, p = ' ' + p;
        vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
        f[0][0] = true;
        for (int i = 0; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (j + 1 <= n && 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] = f[i][j - 2] || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
                }
            }
        }
        return f[m][n];
    }
};

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        s = ' ' + s, p = ' ' + p;
        vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
        f[0][0] = true;
        for (int j = 1; j <= n; j ++) {
            f[0][j] = j >= 2 && p[j] == '*' && f[0][j - 2];
        }

        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (p[j] != '*') {
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                } else if (p[j] == '*') {
                    f[i][j] = j >= 2 && (f[i][j - 2] || f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.'));
                }
            }
        }
        return f[m][n];
    }   
};
#剑指
剑指19：正则表达式匹配
https://lcf163.github.io/2021/01/30/剑指19：正则表达式匹配/
作者
乘风的小站
发布于
2021年1月30日
许可协议