package leetcode;

/**
 * https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
 */
public class Problem712 {
    public int minimumDeleteSum(String s1, String s2) {
        // TODO
        return minimumDeleteSum(s1, s2, s1.length(), s2.length());
    }

    private static int minimumDeleteSum(String s1, String s2, int i, int j) {
        if (i == 0) {
            return Integer.MAX_VALUE;
        }
        if (j == 0) {
            return Integer.MAX_VALUE;
        }
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            return minimumDeleteSum(s1, s2, i - 1, j - 1);
        }
        int ival = 0;
        if (i < s1.length()) {
            ival = s1.charAt(i);
        }
        int jval = 0;
        if (j < s2.length()) {
            jval = s2.charAt(j);
        }
        int a = minimumDeleteSum(s1, s2, i, j - 1);
        if (a == Integer.MAX_VALUE) {
            a = jval;
        } else {
            a += jval;
        }
        int b = minimumDeleteSum(s1, s2, i - 1, j);
        if (b == Integer.MAX_VALUE) {
            b = ival;
        } else {
            b += ival;
        }
        int min = Math.min(a, b);
        return min;
    }

    public static void main(String[] args) {
        Problem712 prob = new Problem712();
        System.out.println(prob.minimumDeleteSum("sea", "eat")); // 231
        System.out.println(prob.minimumDeleteSum("delete", "leet")); // 403
    }
}

@@ -189,15 +189,73 @@
     
-// TODO
+Integer%5B%5D%5B%5D memo = new Integer%5Bs1.length() + 1%5D%5Bs2.length() + 1%5D;
 %0A   
@@ -295,32 +295,18 @@
 s2, 
-s1.length(), s2.length()
+0, 0, memo
 );%0A 
@@ -385,16 +385,34 @@
 i, int j
+, Integer%5B%5D%5B%5D memo
 ) %7B%0A    
@@ -428,79 +428,39 @@
  == 
-0) %7B%0A            return Integer.MAX_VALUE;%0A        %7D%0A        if (j == 0
+s1.length() && j == s2.length()
 ) %7B%0A
@@ -478,33 +478,17 @@
  return 
-Integer.MAX_VALUE
+0
 ;%0A      
@@ -507,157 +507,90 @@
 if (
-s1.charAt(i - 1) == s2.charAt(j - 1)) %7B%0A            return minimumDeleteSum(s1, s2, i - 1, j - 1);%0A        %7D%0A        int ival = 0;%0A        if (i %3C s1
+i == s1.length()) %7B%0A            return s2.charAt(j);%0A        %7D%0A        if (j == s2
 .len
@@ -614,14 +614,14 @@
     
-ival =
+return
  s1.
@@ -654,51 +654,63 @@
    i
-nt jval = 0;%0A        if (j %3C s2.length()) %7B
+f (memo%5Bi%5D%5Bj%5D != null) %7B%0A            return memo%5Bi%5D%5Bj%5D;
 %0A   
@@ -718,17 +718,36 @@
     
+%7D%0A
     
-jval 
+    if (s1.charAt(i) =
 = s2
@@ -760,35 +760,30 @@
 t(j)
-;
+) %7B
 %0A      
-  %7D%0A
       
-  int a =
+return
  min
@@ -809,15 +809,25 @@
 2, i
+ + 1
 , j 
--
++
  1
+, memo
 );%0A 
@@ -837,37 +837,9 @@
     
-if (a == Integer.MAX_VALUE) %7B
+%7D
 %0A   
@@ -847,266 +847,309 @@
     
-   
+int
  a = 
-jval;%0A        %7D else %7B%0A            a += jval;%0A        %7D%0A        int b = minimumDeleteSum(s1, s2, i - 1, j);%0A        if (b == Integer.MAX_VALUE) %7B%0A            b = ival;%0A        %7D else %7B%0A            b += ival;%0A        %7D%0A        int min = Math.min(a, b)
+minimumDeleteSum(s1, s2, i + 1, j, memo) + s1.charAt(i);%0A        int b = minimumDeleteSum(s1, s2, i, j + 1, memo) + s2.charAt(j);%0A        int c = minimumDeleteSum(s1, s2, i + 1, j + 1, memo) + s1.charAt(i) + s2.charAt(j);%0A        int min = Math.min(a, Math.min(b, c));%0A        memo%5Bi%5D%5Bj%5D = min
 ;%0A  

Update problem 712