#### 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 ASCII-sum 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 bottom-up 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.