LeetCode: Minimum ASCII Delete Sum for Two Strings Solution

Approach

Pseudo

1result = totalAscii(s1, s2) - 2 * lcsInAscii(s1, s2)

Implementation

1const lcsInAscii = function (text1, text2) {
2  const memo = Array.from({ length: text1.length + 1 }, _ =>
3    Array(text2.length + 1).fill(null)
4  )
5
6  const recursion = (m, n) => {
7    if (memo[m][n] !== null) return memo[m][n]
8
9    if (m === 0 || n === 0) return (memo[m][n] = 0)
10
11    if (text1[m - 1] === text2[n - 1])
12      return (memo[m][n] = text1[m - 1].charCodeAt(0) + recursion(m - 1, n - 1))
13
14    return (memo[m][n] = Math.max(recursion(m, n - 1), recursion(m - 1, n)))
15  }
16
17  return recursion(text1.length, text2.length)
18}
19
20var minimumDeleteSum = function (s1, s2) {
21  let totalAscii = (s1 + s2)
22    .split("")
23    .reduce((acc, el) => acc + el.charCodeAt(0), 0)
24
25  return totalAscii - 2 * lcsInAscii(s1, s2)
26}

References

Original problem

Similar problems

Edit Distance

Longest Increasing Subsequence

Delete Operation for Two Strings