712. Minimum ASCII Delete Sum for Two Strings

https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/

Python

Bottom-UP DP

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)

        dp = [[0]*(n+1) for _ in range(m+1)]

        for i in range(m-1, -1, -1):
            dp[i][n] = dp[i+1][n] + ord(s1[i])
        for j in range(n-1, -1, -1):
            dp[m][j] = dp[m][j+1] + ord(s2[j])

        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if s1[i] == s2[j]:
                    dp[i][j] = dp[i+1][j+1]
                else:
                    dp[i][j] = min(
                        dp[i+1][j] + ord(s1[i]),
                        dp[i][j+1] + ord(s2[j])
                    )

        return dp[0][0]

JS

var minimumDeleteSum = function(s1, s2) {
    const dp = [...new Array(s2.length + 1)].map(() => new Array(s1.length + 1).fill(0));

    for (let i = 1; i <= s2.length; i++) {
        dp[i][0] = dp[i - 1][0] + s2[i - 1].charCodeAt(0)
    }

    for (let j = 1; j <= s1.length; j++) {
        dp[0][j] = dp[0][j - 1] + s1[j - 1].charCodeAt(0)
    }
    // console.log(dp)

    for (let i = 1; i <= s2.length; i++) {
        for (let j = 1; j <= s1.length; j++) {
            if (s2[i - 1] !== s1[j - 1]) {
                dp[i][j] = Math.min(
                    dp[i - 1][j] + s2[i - 1].charCodeAt(0),
                    dp[i][j - 1] + s1[j - 1].charCodeAt(0)
                );
            } else {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    // console.log(dp)
    return dp[s2.length][s1.length]
};

/**
 *
 *     "   s   e   a
 * "   0 115 216 313
 * e 101 216 115 212
 * a 198 313 212 115
 * t 314 429     231
 *
 * sea, e  -> ["sea", ""] + e or ["se", "e"] + a -> [313 + 116] or [115 + 97]
 * sea, ea -> ["se", "e"] -> 115
 */

// e: 101, a: 97, t: 116, s: 115