leetcode

commit ffcb1c466effc25618faa496e1acec67487e601a
parent 88b59de23f7bea33a9ff2867bef3da09632750e5
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri,  9 Jan 2026 20:39:22 -0700

712. minimum ascii delete sum for two strings

Diffstat:
M
min_ascii_strs.c
 | 
39
+++++++++++++++++----------------------
A
min_ascii_strs.py
 | 
35
+++++++++++++++++++++++++++++++++++

2 files changed, 52 insertions(+), 22 deletions(-)
diff --git a/min_ascii_strs.c b/min_ascii_strs.c
@@ -1,8 +1,5 @@
 // 712. Minimum ASCII Delete Sum for Two Strings
-#include <math.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
+#include "leetcode.h"
 
 /*
  * given two strings 's1' and 's2', return the lowest ascii sum of the deleted
@@ -10,32 +7,30 @@
  */
 
 int minimumDeleteSum(char *s1, char *s2) {
-  int n = strlen(s1), m = strlen(s2), i, j;
-  int **dp = (int **)malloc((n + 1) * sizeof(int *));
-  for (int i = 0; i <= n; i++)
-    dp[i] = (int *)malloc((m + 1) * sizeof(int));
-  dp[0][0] = 0;
-  for (i = 1; i <= m; i++)
-    dp[0][i] = dp[0][i - 1] + s2[i - 1];
-  for (i = 1; i <= n; i++)
-    dp[i][0] = dp[i - 1][0] + s1[i - 1];
-  for (i = 1; i <= n; i++)
-    for (j = 1; j <= m; j++) {
+  int n = strlen(s1), m = strlen(s2);
+  int *dp = (int *)malloc((m + 1) * sizeof(int));
+  for (int i = 1; i <= m; i++)
+    dp[i] = dp[i - 1] + s2[i - 1];
+  for (int i = 1; i <= n; i++) {
+    int t1 = dp[0];
+    dp[0] += s1[i - 1];
+    for (int j = 1; j <= n; j++) {
+      int t2 = dp[j];
       if (s1[i - 1] == s2[j - 1])
-        dp[i][j] = dp[i - 1][j - 1];
+        dp[j] = t1;
       else
-        dp[i][j] = fmin(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
+        dp[j] = fmin(dp[j] + s1[i - 1], dp[j - 1] + s2[j - 1]);
+      t1 = t2;
     }
-  int ans = dp[n][m];
-  for (i = 0; i <= n; i++)
-    free(dp[i]);
+  }
+  int ans = dp[m];
   free(dp);
   return ans;
 }
 
 int main() {
-  char s11[] = {"sea"}, s21[] = {"eat"};
-  char s12[] = {"delete"}, s22[] = {"leet"};
+  char *s11 = "sea", *s21 = "eat";
+  char *s12 = "delete", *s22 = "leet";
   printf("%d\n", minimumDeleteSum(s11, s21)); // expect: 231
   printf("%d\n", minimumDeleteSum(s12, s22)); // expect: 403
 }
diff --git a/min_ascii_strs.py b/min_ascii_strs.py
@@ -0,0 +1,35 @@
+# 712. Minimum ASCII Delete Sum for Two Strings
+
+"""
+given two strings 's1' and 's2', return the lowest ascii sum of the deleted
+characters to make two strings equal
+"""
+
+
+class Solution(object):
+    def minimumDeleteSum(self, s1, s2):
+        """
+        :type s1: str
+        :type s2: str
+        :rtype: int
+        """
+        n, m = len(s1), len(s2)
+        dp = [[0] * (m + 1) for _ in range(n + 1)]
+        for i in range(1, n + 1):
+            for j in range(1, m + 1):
+                if s1[i - 1] == s2[j - 1]:
+                    dp[i][j] = dp[i - 1][j - 1] + ord(s1[i - 1])
+                else:
+                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
+        total = 0
+        for i in s1:
+            total += ord(i)
+        for i in s2:
+            total += ord(i)
+        return total - dp[n][m] * 2
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.minimumDeleteSum(s1="sea", s2="eat"))
+    print(obj.minimumDeleteSum(s1="delete", s2="leet"))