0%

【算法学习】Leetcode 10. 正则表达式匹配

原题链接: Leetcode 10. 正则表达式匹配

题目描述

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

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

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

说明:

s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 .*

解题思路

二维dp

  • 状态表示:
    • dp[i][j]: 字符串s前i个字母能否被p的前j个字母表示
  • 状态计算:
    • 枚举p[j]的所有可能的字母
    • s[i] = p[j]p[j] = '.'
      • dp[i][j] = dp[i - 1][j - 1]
    • p[j] = '*'
      • 不使用*
        • 需要s[1~i]与p[1~j]匹配上:
        • dp[i][j] = dp[i][j - 2]
      • 使用*
        • 需要s[i] = p[j - 1]或者p[j - 1] = .才可以用*
        • 需要s[1 ~ i-1]p[1~j]匹配上
        • dp[i][j] = dp[i - 1][j]

代码:

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
bool isMatch(string s, string p) {
int m, n;
n = s.size(), m = p.size();
// 初始化, 先给s和p加' '不用处理边界
s = ' ' + s;
p = ' ' + p;
// 定义一个n行m列的bool数组, 初始化为false
vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
dp[0][0] = true;

// 先把s为空的情况处理了, 就不用在后面的循环加判断条件处理
for(int i = 2; i <= m; i ++)
{
if(p[i] == '*') dp[0][i] = dp[0][i - 2];
}

for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j++)
{
// 正常转移
if(p[j] == '.' || s[i] == p[j]) dp[i][j] = dp[i - 1][j - 1];
else
{
// 非正常转移
if(p[j] == '*')
{
// 没用到*的情况, 从dp[i][j - 2], 表示*和*前面的数都不使用
dp[i][j] = dp[i][j - 2];
// 用到了*的情况, 从dp[i - 1][j]转移
if(p[j - 1] == '.' || s[i] == p[j - 1]) dp[i][j] = dp[i][j] | dp[i - 1][j];
}
}
}
return dp[n][m];
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def isMatch(self, s: str, p: str) -> bool:
s, p = ' ' + s, ' ' + p
n, m = len(s), len(p)
dp = [[0] * m for _ in range(n)]

dp[0][0] = 1
# p匹配空字符串的特殊情况
for i in range(2, m):
if p[i] == '*':
dp[0][i] = dp[0][i - 2]

for i in range(1, n):
for j in range(1, m):
if (s[i] == p[j] or p[j] == '.'):
dp[i][j] = dp[i - 1][j - 1]
else:
if p[j] == '*':
dp[i][j] = dp[i][j - 2]
if (p[j - 1] == '.' or s[i] == p[j - 1]):
dp[i][j] |= dp[i - 1][j]
return dp[n - 1][m - 1] == 1