Java DP solution!


  • 0
    T
    class Solution {
        public int minimumDeleteSum(String s1, String s2) {
            int[][] dp = new int[s1.length()+1][s2.length()+1];
             
            return findMinSum(s1,s2,s1.length(),s2.length(),dp);
        }
        
        public int findMinSum(String s1,String s2,int len1,int len2,int[][] dp){
            if(dp[len1][len2]!=0){
                return dp[len1][len2];
            }
            
            if(len1==0&&len2==0){
                dp[len1][len2]=0;
                return 0;
            }else if(len1==0){
                int t = findMinSum(s1,s2,0,len2-1,dp);
                dp[0][len2]=t+(int)s2.charAt(len2-1);
                return dp[0][len2];
            }else if(len2==0){
                int t = findMinSum(s1,s2,len1-1,0,dp);
                dp[len1][0]=t+(int)s1.charAt(len1-1);
                return dp[len1][0];
            }
            
            if(s1.charAt(len1-1)==s2.charAt(len2-1)){
                int temp = findMinSum(s1,s2,len1-1,len2-1,dp);
                dp[len1][len2]=temp;
            }else{
                int temp1 = findMinSum(s1,s2,len1,len2-1,dp);
                int temp2 = findMinSum(s1,s2,len1-1,len2,dp);
                dp[len1][len2]=Math.min(temp1+(int)s2.charAt(len2-1),temp2+(int)s1.charAt(len1-1));
            }
            
            return dp[len1][len2];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.