-
Notifications
You must be signed in to change notification settings - Fork 0
/
10. 正则表达式匹配.cpp
104 lines (88 loc) · 4.07 KB
/
10. 正则表达式匹配.cpp
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/*
问题分析:
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
说明:
s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
问题分析:
直觉告诉我dfs会TLE,遂尝试Dp。
对于这种双字符串进行某种模式匹配的Dp,往往是二维Dp
状态选择:
dp[i][j]是bool类型, 表示s的前i个字符能否由p的前j个字符匹配到。
状态转移:
if s[i]==p[j] || p[j]=='.' then:
dp[i][j] = dp[i-1][j-1];
(*) elif p[j]=='*' then:
dp[i][j] = ( s[i]==p[j-1] || p[j-1]=='.' ) && ( dp[i-1][j-1] || dp[i-1][j] || dp[i-1][j-2] )
|| ( j>0 && dp[i][j-2]<0次> )
else dp[i][j] = false;
这里着重讲一下(*)的 s[i]==p[j-1] || p[j-1]=='.' ) && ( dp[i-1][j-1] || dp[i-1][j] || dp[i-1][j-2]
是怎么推的,
假设:
0 ~ i-1 |i
|-----------|▶
|--------|▶ |*
0 ~ j-2 |j-1|j
发现 s[i]==p[j-1]的时候,
如果:
1. s[0~i-1]能够被p[0~j-2]表示出来,那么只要*让▶出现1次,就能够让dp[i][j]为true
即: ----▶
----▶
2. s[0~i-1]能偶被p[0~j-1]表示出来,那么只要*让▶再多出来一个,就能够让dp[i][j]为true
即: ----▶▶
----▶▶
3. s[0~i-1]能够被p[0~j]表示出来,那么只要让*让▶再多出来一个,就能够让dp[i][j]为true
所以只要 s[i]==p[j-1] && (1 or 2 or 3) ,
也就是说 s[i]==p[j-1] && ( dp[i-1][j-1] || dp[i-1][j] || dp[i-1][j-2]
那么dp[i][j]就为true
同时,加上'.'这个通配符,最终变成
s[i]==p[j-1] || p[j-1]=='.' ) && ( dp[i-1][j-1] || dp[i-1][j] || dp[i-1][j-2]
状态转移讲完后,就是dp数组初始化了,
dp[0][0] = true , dp[0][j] = false, dp[i][0] = false;
这些都很好理解,
这里也有个坑,就是如果p的第二个字符是*的话,那么可以让第一个元素不出现,
"" ""
"0*" "1*2*3*"
也是可以匹配成功的,
所以略加改动
for j from 1 to m :
if ( p[j-1]=='*' )
dp[0][j] = dp[0][j-2];
*/
class Solution {
public:
bool isMatch(string s, string p) {
// dp[i][j] 表示s的前i个字符能否由p的前j个字符匹配
int n=s.size(), m=p.size();
if ( n==0 && m==0 ) return true;
vector<vector<bool>> dp(n+1, vector<bool>(m+1, false));
dp[0][0] = true;
for ( int j=1; j<=p.size(); ++j )
if ( p[j-1]=='*' )
dp[0][j] = dp[0][j-2];
for ( int i=1; i<=s.size(); ++i )
for ( int j=1; j<=p.size(); ++j )
if ( s[i-1]==p[j-1] || p[j-1]=='.' )
dp[i][j] = dp[i-1][j-1];
else if ( p[j-1]=='*' )
dp[i][j] = ( (s[i-1]==p[j-2] || p[j-2]=='.' ) && ( dp[i-1][j-2] || dp[i-1][j-1] || dp[i-1][j] ) || j>1 && ( dp[i][j-2] ) ) ;
return dp[n][m];
}
};