Leetcode 712 Minimum ASCII Delete Sum for Two Strings

Telegram Link:

[kushagraahire]

Great explanation. After watching this I solved all the similar problems.

[himanshunegi]

C++ solution

class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
int n = s1.size();
int m = s2.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, 1e6));

dp[0][0] = 0;

for(int i=1;i<=n;i++) dp[i][0] = dp[i-1][0] + (int)s1[i-1];
for(int j=1;j<=m;j++) dp[0][j] = dp[0][j-1] + (int)s2[j-1];

for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1];
}else {
dp[i][j] = min(dp[i-1][j] + (int)s1[i-1], dp[i][j-1] + (int)s2[j-1]);
}
cout << dp[i][j] << ' ';
}
cout << endl;
}
return dp[n][m];
}
};