Q40 Minimum ASCII Delete Sum for Two Strings - LeetCode 712
Tue Mar 28 2023 11:07:11 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int minimumDeleteSum(String s1, String s2) {
//Ques 40 of dp playlist ,minimum ASCCII SUM (MAS)
//every cell will store MAS for ith string to be equal to jth string
int m = s1.length() , n = s2.length();
int[][] dp = new int[m+1][n+1]; //+1 for empty string
//last row and last col will be 0
for(int i = m; i>=0 ;i--){
for(int j = n ; j>=0 ; j--){
//last cell
if(i == m && j == n)
dp[i][j] = 0;
//last col, it will be down cell + ASCII of current character
else if(j == n)
dp[i][j] = dp[i+1][j] + (int)s1.charAt(i);
//last row, it will be right cell + ASCII of current character
else if(i == m)
dp[i][j] = dp[i][j+1] + (int)s2.charAt(j);
//ROD - rest of the dp
else{
if(s1.charAt(i) == s2.charAt(j))
dp[i][j] = dp[i+1][j+1];
/*removing first char of str1 and checking MAS with ros str2
and vice versa ...and taking minimum of both while adding
the ascii value of character removed
*/
else{
int MAS1 = dp[i+1][j] + (int)(s1.charAt(i));
int MAS2 = dp[i][j+1] + (int)(s2.charAt(j));
dp[i][j] = Math.min(MAS1 , MAS2);
}
}
}
}
return dp[0][0];
}
}
content_copyCOPY
https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
Comments