leetcode

commit 0f0efc725350972d6bee80b4c2a0927bf923f3dd
parent 9ec6d024c55822ec5aba1bf027e85d23b33a56a0
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 25 May 2024 16:28:34 +0200

Daily Problem

Diffstat:
A
Problems/0140.cpp
 | 
28
++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 29 insertions(+), 0 deletions(-)
diff --git a/Problems/0140.cpp b/Problems/0140.cpp
@@ -0,0 +1,28 @@
+class Solution {
+    unordered_set<string> us[10];
+
+    vector<string> rec(const string &s, const int start = 0) {
+        const int n = size(s);
+        vector<string> res;
+        string crnt;
+
+        if (start == n) return {""};
+        for (int i = start; i < min(start + 10, n); i++) {
+            crnt += s[i];
+            if (!us[i - start].count(crnt)) continue;
+            for (const auto &s : rec(s, i + 1)) {
+                res.push_back(start == 0 ? "" : " ");
+                res.back() += crnt + s;
+            }
+        }
+
+        return res;
+    }
+
+  public:
+    vector<string> wordBreak(const string &s, const vector<string> &wordDict) {
+        for (const auto &word : wordDict)
+            us[size(word) - 1].insert(word);
+        return rec(s);
+    }
+};
diff --git a/README.md b/README.md
@@ -159,6 +159,7 @@ for solving problems.
 |  0137  |   Medium   | [Single Number II](Problems/0137.cpp)                                                              |
 |  0138  |   Medium   | [Copy List with Random Pointer](Problems/0138.cpp)                                                 |
 |  0139  |   Medium   | [Word Break](Problems/0139.cpp)                                                                    |
+|  0140  |    Hard    | [Word Break II](Problems/0140.cpp)                                                                 |
 |  0141  |    Easy    | [Linked List Cycle](Problems/0141.cpp)                                                             |
 |  0142  |   Medium   | [Linked List Cycle II](Problems/0142.cpp)                                                          |
 |  0143  |   Medium   | [Reorder List](Problems/0143.cpp)                                                                  |