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]; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter