diff options
| author | crupest <crupest@outlook.com> | 2021-02-23 21:07:19 +0800 |
|---|---|---|
| committer | crupest <crupest@outlook.com> | 2021-02-23 21:07:19 +0800 |
| commit | d8f3b40085619cb680c8f227c65a1f5acc393223 (patch) | |
| tree | 6a38e3a6c79276fc396259ef962d17236dbed569 /cpp/10.cpp | |
| parent | b0162802ad9723c678e495f29ca2f0fc0af2eff1 (diff) | |
| download | solutions-d8f3b40085619cb680c8f227c65a1f5acc393223.tar.gz solutions-d8f3b40085619cb680c8f227c65a1f5acc393223.tar.bz2 solutions-d8f3b40085619cb680c8f227c65a1f5acc393223.zip | |
Move leetcode solutions to subdir.
Diffstat (limited to 'cpp/10.cpp')
| -rw-r--r-- | cpp/10.cpp | 83 |
1 files changed, 0 insertions, 83 deletions
diff --git a/cpp/10.cpp b/cpp/10.cpp deleted file mode 100644 index fbb5586..0000000 --- a/cpp/10.cpp +++ /dev/null @@ -1,83 +0,0 @@ -#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;
- }
- }
- }
- }
-};
|