Approach #1: Dynamic Programming [Accepted]
Intuition and Algorithm
Let dp[i][j]
be the answer to the problem for the strings s1[i:], s2[j:]
.
When one of the input strings is empty, the answer is the ASCIIsum of the other string. We can calculate this cumulatively using code like dp[i][s2.length()] = dp[i+1][s2.length()] + s1.codePointAt(i)
.
When s1[i] == s2[j]
, we have dp[i][j] = dp[i+1][j+1]
as we can ignore these two characters.
When s1[i] != s2[j]
, we will have to delete at least one of them. We'll have dp[i][j]
as the minimum of the answers after both deletion options.
The solutions presented will use bottomup dynamic programming.
Python
class Solution(object): def minimumDeleteSum(self, s1, s2): dp = [[0] * (len(s2) + 1) for _ in xrange(len(s1) + 1)] for i in xrange(len(s1)  1, 1, 1): dp[i][len(s2)] = dp[i+1][len(s2)] + ord(s1[i]) for j in xrange(len(s2)  1, 1, 1): dp[len(s1)][j] = dp[len(s1)][j+1] + ord(s2[j]) for i in xrange(len(s1)  1, 1, 1): for j in xrange(len(s2)  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]
Java
class Solution { public int minimumDeleteSum(String s1, String s2) { int[][] dp = new int[s1.length() + 1][s2.length() + 1]; for (int i = s1.length()  1; i >= 0; i) { dp[i][s2.length()] = dp[i+1][s2.length()] + s1.codePointAt(i); } for (int j = s2.length()  1; j >= 0; j) { dp[s1.length()][j] = dp[s1.length()][j+1] + s2.codePointAt(j); } for (int i = s1.length()  1; i >= 0; i) { for (int j = s2.length()  1; j >= 0; j) { if (s1.charAt(i) == s2.charAt(j)) { dp[i][j] = dp[i+1][j+1]; } else { dp[i][j] = Math.min(dp[i+1][j] + s1.codePointAt(i), dp[i][j+1] + s2.codePointAt(j)); } } } return dp[0][0]; } }
Complexity Analysis

Time Complexity: , where are the lengths of the given strings. We use nested for loops: each loop is and respectively.

Space Complexity: , the space used by
dp
.
Analysis written by: @awice.