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
|
#include <string>
#include <unordered_map>
#include <vector>
using std::string;
struct Token {
explicit Token(char c) : c(c), isAsterisk(false) {}
char c;
bool isAsterisk;
};
class Solution {
public:
std::vector<Token> tokens_;
std::string s_;
std::unordered_map<int, std::unordered_map<int, int>> cache_;
bool isMatch(string s, string p) {
for (auto c : p) {
if (c == '*') {
tokens_.back().isAsterisk = true;
} else {
tokens_.push_back(Token{c});
}
}
s_ = s;
return match(0, 0, s_.size(), tokens_.size());
}
bool cache_match(int s_start, int t_start, int s_length, int t_length) {
auto cache = cache_[s_start][t_start];
if (cache < 0) {
return false;
} else if (cache > 0) {
return true;
} else {
auto result = match(s_start, t_start, s_length, t_length);
cache_[s_start][t_start] = result;
return result;
}
}
bool match(int s_start, int t_start, int s_length, int t_length) {
if (t_start == t_length)
return s_start == s_length;
const auto &token = tokens_[t_start];
if (token.isAsterisk) {
if (cache_match(s_start, t_start + 1, s_length, t_length)) {
return true;
}
int s_index = s_start;
while (s_index < s_length) {
if (token.c == '.') {
if (cache_match(s_index + 1, t_start + 1, s_length, t_length))
return true;
} else if (token.c == s_[s_index]) {
if (cache_match(s_index + 1, t_start + 1, s_length, t_length))
return true;
} else {
break;
}
s_index++;
}
return false;
} else {
if (token.c == '.') {
return cache_match(s_start + 1, t_start + 1, s_length, t_length);
} else {
if (token.c == s_[s_start]) {
return cache_match(s_start + 1, t_start + 1, s_length, t_length);
} else {
return false;
}
}
}
}
};
|
