#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/lcs-and-edit-distance/min-ascii-delete-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/lcs-and-edit-distance/min-ascii-delete-implementation

Repovive

LeetCode 712 Minimum ASCII Delete Sum for Two Strings - Implementation - LCS and Edit Distance | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 712 Minimum ASCII Delete Sum for Two Strings - Implementation

The code

Here's the full solution:

function minimumDeleteSum(s1, s2)
    m := length of s1
    n := length of s2
    dp := 2D (two-dimensional) array (m + 1) x (n + 1)
    dp[0][0] := 0
    for i from 1 to m
        dp[i][0] := dp[i - 1][0] + ASCII(s1[i - 1])
    for j from 1 to n
        dp[0][j] := dp[0][j - 1] + ASCII(s2[j - 1])
    for i from 1 to m
        for j from 1 to n
            if s1[i - 1] = s2[j - 1]
                dp[i][j] := dp[i - 1][j - 1]
            else
                dp[i][j] := min(dp[i - 1][j] + ASCII(s1[i - 1]), dp[i][j - 1] + ASCII(s2[j - 1]))
    return dp[m][n]

Time: $O(mn)$ . Space: $O(mn)$ .

The base cases sum ASCII values of deleted characters. The transition minimizes deletion cost: either delete from s1 or s2.