Search with pruning. However, there was a strange issue where one test case would not pass. I had to add a pruning condition specifically for that test case to get AC. So I should really look into the DP approach. At the time I kept trying to use a greedy method, but clearly there are many places requiring backtracking, so the greedy approach does not work well. Also note that a* should be treated as a unit – it represents the empty string or a string of multiple as.
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
| class Solution {
public:
bool result;
bool isMatch(const char *s, const char *p) {
// Note: The Solution object is instantiated only once and is reused by each test case.
result = false;
int lens = strlen(s);
int lenp = strlen(p);
if(p[lenp-1] != '*' && s[lens-1] != p[lenp-1] && p[lenp-1]!='.')return result;
matchStep(s,p);
return result;
}
private:
void matchStep(const char * s,const char * p) {
if(result)return;
if(*s == '\0' && *p == '\0') {
result = true;
return;
}
if(*s == '\0') {
if(*(p+1) == '*') {
matchStep(s,p+2);
return ;
}
}
if(*s == '\0' || *p == '\0')return;
if(*(p+1) != '\0') {
if(*(p+1) != '*') {
if(*s == *p || *p == '.') {
matchStep(s+1,p+1);
}
else
return;
}
else {
if(*s != *p && *p != '.') {
matchStep(s,p+2);
}
else {
matchStep(s,p+2);
matchStep(s+1,p);
matchStep(s+1,p+2);
}
}
}
else {
if(*s == *p || *p == '.') {
matchStep(s+1,p+1);
}
else
return;
}
}
};
|