leetcode

commit efcdbeb12bf1d09be98e127d8a154c4049797fb2
parent b9380b2758109dc635a18825071caebfcaba6d5f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat,  2 Sep 2023 11:41:44 +0200

Daily Problem

Diffstat:
A
Problems/2707.cpp
 | 
18
++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 19 insertions(+), 0 deletions(-)
diff --git a/Problems/2707.cpp b/Problems/2707.cpp
@@ -0,0 +1,18 @@
+class Solution {
+  public:
+    int minExtraChar(const string &s, const vector<string> &dictionary) {
+        unordered_set<string> us(begin(dictionary), end(dictionary));
+        int dp[51] = {0};
+
+        for (int i = s.size() - 1; i >= 0; i--) {
+            int mini = s.size();
+            for (int j = i; j < s.size(); j++) {
+                int crnt = us.count(s.substr(i, j - i + 1)) ? 0 : j - i + 1;
+                mini = min(mini, dp[j + 1] + crnt);
+            }
+            dp[i] = mini;
+        }
+
+        return *begin(dp);
+    }
+};
diff --git a/README.md b/README.md
@@ -727,6 +727,7 @@ for solving problems.
 |  2666  |    Easy    | [Allow One Function Call](Problems/2666.js)                                                      |
 |  2667  |    Easy    | [Create Hello World Function](Problems/2667.js)                                                  |
 |  2676  |   Medium   | [Throttle](Problems/2676.js)                                                                     |
+|  2707  |   Medium   | [Extra Characters in a String](Problems/2707.cpp)                                                |
 |  2711  |   Medium   | [Difference of Number of Distinct Values on Diagonals](Problems/2711.cpp)                        |
 |  2785  |   Medium   | [Sort Vowels in a String](Problems/2785.cpp)                                                     |
 |  2807  |   Medium   | [Insert Greatest Common Divisors in Linked List](Problems/2807.cpp)                              |