Repository navigation
Expand file tree
/
Copy pathRegularExpressionMatching.cpp
More file actions
103 lines (93 loc) · 2.03 KB
/
Copy pathRegularExpressionMatching.cpp
File metadata and controls
103 lines (93 loc) · 2.03 KB
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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
// recursion
/*bool isMatch(const char *s, const char *p) {
if (s == NULL || p == NULL) {
return false;
}
if (*p == '\0') {
return *s == '\0';
}
if (p[1] != '*') {
if (s[0] == p[0] || (p[0] == '.' && s[0] != '\0')) {
return isMatch(s+1, p+1);
} else {
return false;
}
} else {
while (*s == p[0] || (p[0] == '.' && *s != '\0')) {
if (isMatch(s, p+2)) {
return true;
}
++s;
}
}
return isMatch(s, p+2);
}*/
// dp
void print(vector<vector<bool> > matrix) {
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[0].size(); ++j) {
cout << matrix[i][j] << " ";
}puts("");
}
}
bool isMatch(const char *s, const char *p) {
if (s == NULL || p == NULL) {
return false;
}
if (*p == '\0') {
return *s == '\0';
}
int slen = strlen(s);
int plen = strlen(p);
vector<vector<bool> > isMatch(plen+1, vector<bool>(slen+1, false));
// initialize
for (int i = 1; i <= slen; ++i) {
isMatch[0][i] = false;
}
bool matchTmp = true;
isMatch[0][0] = true;
isMatch[1][0] = false;
// the reason to start from 2 is to avoid special case that the first character of p is '*'
// here we assume that '*' greedily match the preceding one;
for (int i = 2; i <= plen; ++i) {
if (matchTmp && p[i-1] == '*') {
isMatch[i][0] = true;
} else {
if (i%2 == 0) {
matchTmp = false;
}
isMatch[i][0] = false;
}
}
for (int i = 1; i <= plen; ++i) {
for (int j = 1; j <= slen; ++j) {
if (p[i-1] == '*' && i > 1) {
for (int k = 0; k <= j; ++k) { // length for x* to match
if (p[i-2] == '.' || k == 0 || (p[i-2] == s[j-k])) {
if (isMatch[i-2][j-k]) {
isMatch[i][j] = true;
break;
}
} else {
break;
}
}
} else {
isMatch[i][j] = isMatch[i-1][j-1] && (p[i-1]==s[j-1] || (p[i-1] == '.'));
}
}
}
print(isMatch);
return isMatch[plen][slen];
}
int main() {
char a[] = "aa";
char b[] = "a";
cout << isMatch(a, b) << endl;
return 0;
}