leetcode

commit b81cb4910ddbc001f0a49fd43d46d1f196c47a21
parent 04e6243c32ea467babf67893b2ec92c90a7d1511
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 15 Jun 2024 13:39:14 +0200

1 Random Problem

Diffstat:
A
Problems/0792.cpp
 | 
26
++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 27 insertions(+), 0 deletions(-)
diff --git a/Problems/0792.cpp b/Problems/0792.cpp
@@ -0,0 +1,26 @@
+class Solution {
+  public:
+    int numMatchingSubseq(const string &s, const vector<string> &words) const {
+        static int pos[50001][26];
+        const int n = size(s);
+        int res = 0;
+
+        memset(pos[n], 0x00, sizeof(pos[n]));
+        for (int i = n - 1; i >= 0; i--) {
+            memcpy(pos[i], pos[i + 1], sizeof(pos[i]));
+            pos[i][s[i] - 'a'] = i + 1;
+        }
+
+        for (const auto &word : words) {
+            int crnt = 0;
+            for (const char c : word) {
+                if (!pos[crnt][c - 'a']) goto next;
+                crnt = pos[crnt][c - 'a'];
+            }
+            res++;
+        next:;
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -497,6 +497,7 @@ for solving problems.
 |  0789  |   Medium   | [Escape The Ghosts](Problems/0789.cpp)                                                             |
 |  0790  |   Medium   | [Domino and Tromino Tiling](Problems/0790.cpp)                                                     |
 |  0791  |   Medium   | [Custom Sort String](Problems/0791.cpp)                                                            |
+|  0792  |   Medium   | [Number of Matching Subsequences](Problems/0792.cpp)                                               |
 |  0795  |   Medium   | [Number of Subarrays with Bounded Maximum](Problems/0795.cpp)                                      |
 |  0797  |   Medium   | [All Paths From Source to Target](Problems/0797.cpp)                                               |
 |  0799  |   Medium   | [Champagne Tower](Problems/0799.cpp)                                                               |