java concise DP


  • 0
    S
    class Solution {
        //
        // opt[i][j] =   not same at ends, delete char at end of s1 opt[i-1][j] +  s1.charAt(i)
        //                      or  delete char at end of s2 opt[i][j-1] + s2.charAt(j)
        //                   same at both end, keep both char opt[i-1][j-1]
        
        public int minimumDeleteSum(String s1, String s2) {
            int[][] opt = new int[s1.length() + 1][s2.length() + 1];
            opt[0][0] = 0; // empty both
            for (int i = 1; i <= s1.length(); i++) {
                opt[i][0] = opt[i-1][0] + s1.charAt(i - 1);
            }
            for (int j = 1; j <= s2.length(); j++) {
                opt[0][j] = opt[0][j-1] + s2.charAt(j - 1);
            }
            
            for (int i = 1; i <= s1.length(); i++) {
                for (int j = 1; j <= s2.length(); j++) {
                    char s1c = s1.charAt(i-1);
                    char s2c = s2.charAt(j-1);
                    if (s1c == s2c) opt[i][j] = opt[i-1][j-1];
                    else {
                        opt[i][j] = Math.min(opt[i-1][j] + s1c, opt[i][j-1] + s2c);
                    }
                }
            }
            return opt[s1.length()][s2.length()];
            
        }
    }
    

Log in to reply
 

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