-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path10_regular_expression_matching.cc
125 lines (122 loc) · 4.84 KB
/
10_regular_expression_matching.cc
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace::std;
class Solution {
public:
bool isMatch(string s, string p) {
// s.push_back('a');
// s.push_back('a');
// p.push_back('a');
// p.push_back('a');
auto s_size = s.size(), p_size = p.size();
if (p_size == 0) {
return s_size == 0 ? true : false;
} else if (p_size == 1) {
if (s_size == 1) {
if (p[0] == '.' || p[0] == s[0])
return true;
}
return false;
} else {
if (s_size == 0) {
for (unsigned i = 0; i < p_size; ) {
if (p[i] == '*')
++i;
else if (i == p_size - 1 || p[i + 1] != '*')
return false;
else
i += 2;
}
return true;
} else {
vector<vector<int>> dp(p_size, vector<int> (s_size + 1, 0));
for (unsigned i = 0; i < p_size; ) {
if (i == p_size - 1) {
// cout << "---------------------- last" << endl;
if ((p[i] == '.' || p[i] == s[s_size - 1]) && dp[i - 1][s_size - 1])
return true;
return false;
} else {
if (p[i] == '.' && p[i + 1] == '*') {
// cout << "---------------------- 1" << endl;
if (i == 0) {
for (int j = 0; j < (int)s_size + 1; ++j)
dp[i + 1][j] = 1;
} else {
int pre_match = 0;
for (int j = 0; j < (int)s_size + 1; ++j) {
if (dp[i - 1][j])
pre_match = 1;
if (pre_match)
dp[i + 1][j] = 1;
}
}
i += 2;
} else if (p[i + 1] == '*') {
// cout << "---------------------- 2" << endl;
if (i == 0) {
dp[i + 1][0] = 1;
for (unsigned k = 0; k < s_size && p[i] == s[k]; ++k)
dp[i + 1][k + 1] = 1;
} else {
int pre_match = 0;
for (unsigned j = 0; j < s_size + 1; ) {
if (dp[i - 1][j])
pre_match = 1;
if (pre_match) {
dp[i + 1][j++] = 1;
for (; j < s_size + 1 && p[i] == s[j - 1]; ++j)
dp[i + 1][j] = 1;
pre_match = 0;
} else
++j;
}
}
i += 2;
} else if (p[i] == '.') {
// cout << "---------------------- 3" << endl;
if (i == 0)
dp[i][1] = 1;
else {
for (unsigned j = 0; j < s_size; ++j) {
if (dp[i - 1][j])
dp[i][j + 1] = 1;
}
}
++i;
} else {
// cout << "---------------------- 4" << endl;
if (i == 0) {
if (p[0] != s[0])
return false;
else
dp[0][1] = 1;
}
else {
for (unsigned j = 0; j < s_size; ++j) {
if (dp[i - 1][j] && p[i] == s[j] )
dp[i][j + 1] = 1;
}
}
++i;
}
}
}
if (dp[p_size - 1][s_size])
return true;
else
return false;
}
}
}
};
int main()
{
Solution solu;
string s, p;
cin >> s >> p;
cout << solu.isMatch(s, p) << endl;
return 0;
}