712. Minimum ASCII Delete Sum for Two Strings

minimum-ascii-delete-sum-for-two-strings.md

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

• Input: s1 = "sea", s2 = "eat"
• Output: 231
• Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum. Deleting "t" from "eat" adds 116 to the sum. At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

• Input: s1 = "delete", s2 = "leet"
• Output: 403
• Explanation: Deleting "dee" from "delete" to turn the string into "let", adds 100[d]+101[e]+101[e] to the sum. Deleting "e" from "leet" adds 101[e] to the sum. At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403. If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.

Note:

• 0 < s1.length, s2.length <= 1000.
• All elements of each string will have an ASCII value in [97, 122].

Scala solution for edit distances:

case class Edit(cost: Int, action: String, parent: Edit) {
  override def toString: String = s"($cost) $action"
}

def func(s: String, t: String): Unit = {
  def print(arr: Array[Array[Edit]]): Unit = {
    for (l <- arr) {
      println(l.mkString("[", ", \t", "]"))
    }
  }

  def reconstruct(edit: Edit): Unit = {
    if (edit == null) return
    reconstruct(edit.parent)
    println(edit.toString)
  }

  def match_cost(a: Char, b: Char): Int = if (a == b) 0 else a + b
  def del_cost(a: Char): Int = a
  
  val n = s.length
  val m = t.length
  val dp = (0 to n).map { i => new Array[Edit](m + 1) }.toArray

  dp(0)(0) = Edit(0, "", null)
  var sum = 0
  var prev: Edit = null
  for (i <- 1 until n + 1) { 
    sum += s.charAt(i-1) 
    dp(i)(0) = Edit(sum, s"DEL ${s.charAt(i-1)}", prev)
    prev = dp(i)(0)
  }
  sum = 0
  prev = null
  for (j <- 1 until m + 1) { 
    sum += t.charAt(j-1) 
    dp(0)(j) = Edit(sum, s"DEL ${t.charAt(j-1)}", prev)
    prev = dp(0)(j)
  }

  for (i <- 1 until n + 1) {
    for (j <- 1 until m + 1) {
      val a = s.charAt(i-1)
      val b = t.charAt(j-1)
      val cost1 = dp(i-1)(j-1).cost + match_cost(a, b)
      val cost2 = dp(i)(j-1).cost + del_cost(b)
      val cost3 = dp(i-1)(j).cost + del_cost(a)
      dp(i)(j) = Array(
        Edit(cost1, if (a != b) s"SUB $a != $b" else s"MAT $a = $b", dp(i-1)(j-1)), 
        Edit(cost2, s"INS $b", dp(i)(j-1)),
        Edit(cost3, s"DEL $a", dp(i-1)(j))
      ).sortWith(_.cost < _.cost).head
    }
  }
  
  print(dp)
  println("Actions: ")
  reconstruct(dp(n)(m))
}

func("a", "z")
func("xyz", "za")
func("delete", "leet")

Actual solution to the problem:

// Solution runs in O(n * m) time and O(n * m) space, beats 73.92% of submissions.
//
// Idea is based on Dynamic Programming "Edit distance" technique, because we can think of this
// problem as, instead of deleting from both strings, we select "s2" as target and perform
// substitution, deletion or insertion on "s1" string.
//
// Our cost function is based on ASCII character code, so the smaller code is the better.
// Initialization is similar: first row and first column are both initialized as rolling sums of
// ASCII codes for "s1" and "s2" strings respectively (which represents deletion of all i-1 chars
// at position i, when the other string has j=0 and vice versa).
//
class Solution {
  public int minimumDeleteSum(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    int[][] dp = new int[n + 1][m + 1];

    // initialize first row and first column
    for (int i = 1; i <= n; i++) {
      dp[i][0] = dp[i-1][0] + s1.charAt(i-1);
    }
    for (int j = 1; j <= m; j++) {
      dp[0][j] = dp[0][j-1] + s2.charAt(j-1);
    }

    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        char a = s1.charAt(i-1), b = s2.charAt(j-1);
        dp[i][j] = dp[i-1][j-1] + ((a == b) ? 0 : (a + b)); // match or substitution
        dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + a); // delete from s1
        dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + b); // delete from s2 (insert into s1)
      }
    }
    return dp[n][m];
  }
}