-
Notifications
You must be signed in to change notification settings - Fork 28
/
Regular_Expression_Matching.cpp
69 lines (67 loc) · 2.03 KB
/
Regular_Expression_Matching.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
// using dp.. dp isn't very fast here as range is small
class Solution {
bool isMatch(string const& s, int i, string const& p, int j, vector<vector<int>>& dp) {
int m = (int)p.length(), n = (int)s.length();
if(j == m) {
return (i == n);
}
if(dp[i][j] != -1) {
return dp[i][j];
}
if(j < m - 1 and p[j + 1] == '*') {
if(isMatch(s, i, p, j + 2, dp)) {
return dp[i][j] = true;
}
while(i < n and (p[j] == '.' or p[j] == s[i])) {
if(isMatch(s, i + 1, p, j + 2, dp)) {
return dp[i][j] = true;
}
i++;
}
} else {
if(i == n) {
return false;
}
if(p[j] == '.' or p[j] == s[i]) {
return dp[i][j] = isMatch(s, i + 1, p, j + 1, dp);
}
}
return dp[i][j] = false;
}
public:
bool isMatch(string s, string p) {
int n = (int)s.length();
int m = (int)p.length();
vector<vector<int>> dp(n + 1, vector<int>(m, -1));
return isMatch(s, 0, p, 0, dp);
}
};
// copying substring as function argument(slower)
class Solution {
public:
bool isMatch(string s, string p) {
if(p.length() == 0) {
return s.length() == 0;
}
if(p.length() > 1 && p[1] == '*') {
if(isMatch(s, p.substr(2))) {
return true;
}
int i = 0;
while(i < s.length() && (p[0] == '.' || p[0] == s[i])) {
if(isMatch(s.substr(i + 1), p.substr(2))) {
return true;
}
++i;
}
return false;
}
else {
if(s.length() == 0)
return false;
if(p[0] != '.' && p[0] != s[0])
return false;
return isMatch(s.substr(1), p.substr(1));
}
}
};