leetcode

commit ff0a26a04244dca9e4973c958dc92f3751aed48e
parent 8541556871fc3e0428f02f3e6e784bf020cf2d1d
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu,  6 Jun 2024 23:30:40 +0200

1 Random Problem

Diffstat:
A
Problems/0524.cpp
 | 
32
++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 33 insertions(+), 0 deletions(-)
diff --git a/Problems/0524.cpp b/Problems/0524.cpp
@@ -0,0 +1,32 @@
+class Solution {
+  public:
+    string findLongestWord(const string &s, const vector<string> &dictionary) const {
+        static int count[1001][26];
+        const int n = size(s);
+        string res;
+
+        memset(count[n], 0x00, sizeof(count[n]));
+        for (int i = n - 1; i >= 0; i--) {
+            memcpy(count[i], count[i + 1], sizeof(count[n]));
+            count[i][s[i] - 'a'] = i + 1;
+        }
+
+        for (const auto &word : dictionary) {
+            int pos = 0;
+            for (const char c : word) {
+                const int idx = c - 'a';
+                if (!count[pos][idx]) goto next;
+                pos = count[pos][idx];
+            }
+
+            if (size(word) > size(res))
+                res = word;
+            else if (size(word) == size(res))
+                res = min(res, word);
+
+        next:;
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -371,6 +371,7 @@ for solving problems.
 |  0516  |   Medium   | [Longest Palindromic Subsequence](Problems/0516.cpp)                                               |
 |  0518  |   Medium   | [Coin Change II](Problems/0518.cpp)                                                                |
 |  0520  |    Easy    | [Detect Capital](Problems/0520.cpp)                                                                |
+|  0524  |   Medium   | [Longest Word in Dictionary through Deleting](Problems/0524.cpp)                                   |
 |  0525  |   Medium   | [Contiguous Array](Problems/0525.cpp)                                                              |
 |  0526  |   Medium   | [Beautiful Arrangement](Problems/0526.cpp)                                                         |
 |  0529  |   Medium   | [Minesweeper](Problems/0529.cpp)                                                                   |