-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathisMatch2.cc
More file actions
32 lines (32 loc) · 726 Bytes
/
isMatch2.cc
File metadata and controls
32 lines (32 loc) · 726 Bytes
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
bool isMatch(const char *s, const char *p) {
int n = strlen(s), m = strlen(p);
int *cur = new int[n + 1];
int *nxt = new int[n + 1];
for (int i = 0; i <= n; i++) cur[i] = (i == 0);
for (int i = 0; i < m; i++) {
for (int j = 0; j <= n; j++) nxt[j] = 0;
char c = p[i];
if (c == '*') {
int value = cur[0];
nxt[0] = cur[0];
for (int j = 0; j < n; j++) {
value |= cur[j + 1];
nxt[j + 1] = value;
}
} else {
for (int j = 0; j < n; j++) {
if (s[j] == c || c == '?') {
nxt[j + 1] = cur[j];
}
}
}
int *temp;
temp = cur;
cur = nxt;
nxt = temp;
}
int ans = cur[n];
delete cur;
delete nxt;
return ans;
}