Leetcode Problem 712. Minimum ASCII Delete Sum for Two Strings

712. Minimum ASCII Delete Sum for Two Strings

Leetcode Solutions

Dynamic Programming - Bottom-up Approach

  1. Initialize a two-dimensional array dp of size (m+1) x (n+1) where m and n are the lengths of s1 and s2 respectively.
  2. Fill the first row of dp with the cumulative ASCII sum of characters in s1.
  3. Fill the first column of dp with the cumulative ASCII sum of characters in s2.
  4. Iterate over the array starting from dp[1][1] to dp[m][n].
    • If s1[i-1] == s2[j-1], set dp[i][j] = dp[i-1][j-1].
    • Otherwise, set dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])).
  5. Return dp[m][n] as the final result.
UML Thumbnail

Dynamic Programming - Top-down Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...