LeetCode10 正则表达式匹配

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

题面

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

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

    解法

    设立状态dp[i][j]表示s的前i个字符和p的前j个字符是否可以匹配
    考虑状态转移方式,有以下几种情况
  1. p[j]是’.’ 即可以匹配任意字符 这种情况下只需要考虑s和p之前的字符串是否可以匹配 $ dp[i][j] = dp[i - 1][j - 1] $
  2. p[j]是普通字符 这是只需要考虑s[i - 1]和p[j - 1]是否相同 并且之前的字符串是否可以匹配 $ dp[i][j] = (dp[i - 1][j - 1]) and (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 以及 dp[i - 1]j
    • 另一种情况是p[j - 2] 和 s[i - 1] 无法匹配(两者不同且p[j - 1]不是’.’) 这个时候只能考虑将*扩充为零个字符 $dp[i][j] = dp[i][j - 2]$

代码

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];

}
};