leetcode

commit ed4d5136e5d7161ea0da3b487d41bf822855c3a4
parent 0c50ff9dddd1b1e1715044ade0c32d80961059c6
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 31 Jul 2023 14:30:17 +0200

Daily Problem

Diffstat:
A
Problems/0712.cpp
 | 
25
+++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 26 insertions(+), 0 deletions(-)
diff --git a/Problems/0712.cpp b/Problems/0712.cpp
@@ -0,0 +1,25 @@
+class Solution {
+  int dp[1001][1001];
+  int rec(const string &s1, const string &s2, int l1, int l2) {
+    if (l1 >= s1.size() && l2 >= s2.size()) return 0;
+    if (dp[l1][l2] != -1) return dp[l1][l2];
+
+    int res = INT_MAX;
+    if (s1[l1] == s2[l2]) res = min(res, rec(s1, s2, l1 + 1, l2 + 1));
+    res = min(res, s1[l1] + rec(s1, s2, l1 + 1, l2));
+    res = min(res, s2[l2] + rec(s1, s2, l1, l2 + 1));
+
+    return dp[l1][l2] = res;
+  }
+
+public:
+  Solution() { memset(dp, 0xFF, sizeof(dp)); }
+  int minimumDeleteSum(const string &s1, const string &s2) {
+    for (int i = s1.size() - 1, sum = 0; i >= 0; i--)
+      dp[i][s2.size()] = sum += s1[i];
+    for (int i = s2.size() - 1, sum = 0; i >= 0; i--)
+      dp[s1.size()][i] = sum += s2[i];
+
+    return rec(s1, s2, 0, 0);
+  }
+};
diff --git a/README.md b/README.md
@@ -342,6 +342,7 @@ for solving problems.
 |  0705  |    Easy    | [Design HashSet](Problems/0705.cpp)                                                              |
 |  0706  |    Easy    | [Design HashMap](Problems/0706.cpp)                                                              |
 |  0707  |   Medium   | [Design Linked List](Problems/0707.cpp)                                                          |
+|  0712  |   Medium   | [Minimum ASCII Delete Sum for Two Strings](Problems/0712.cpp)                                    |
 |  0713  |   Medium   | [Subarray Product Less Than K](Problems/0713.cpp)                                                |
 |  0714  |   Medium   | [Best Time to Buy and Sell Stock with Transaction Fee](Problems/0714.cpp)                        |
 |  0724  |    Easy    | [Find Pivot Index](Problems/0724.cpp)                                                            |