1 files changed, 83 insertions, 0 deletions
diff --git a/works/solutions/cpp/10.cpp b/works/solutions/cpp/10.cpp
new file mode 100644
index 0000000..fbb5586
--- /dev/null
+++ b/works/solutions/cpp/10.cpp
@@ -0,0 +1,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;
+        }
+      }
+    }
+  }
+};