@@ -0,0 +1,1472 @@
+// Solution runs in O(n * m) time and O(n * m) space, beats 73.92%25 of submissions.%0A//%0A// Idea is based on Dynamic Programming %22Edit distance%22 technique, because we can think of this%0A// problem as, instead of deleting from both strings, we select %22s2%22 as target and perform%0A// substitution, deletion or insertion on %22s1%22 string.%0A//%0A// Our cost function is based on ASCII character code, so the smaller code is the better.%0A// Initialization is similar: first row and first column are both initialized as rolling sums of%0A// ASCII codes for %22s1%22 and %22s2%22 strings respectively (which represents deletion of all i-1 chars%0A// at position i, when the other string has j=0 and vice versa).%0A//%0Aclass Solution %7B%0A  public int minimumDeleteSum(String s1, String s2) %7B%0A    int n = s1.length(), m = s2.length();%0A    int%5B%5D%5B%5D dp = new int%5Bn + 1%5D%5Bm + 1%5D;%0A%0A    // initialize first row and first column%0A    for (int i = 1; i %3C= n; i++) %7B%0A      dp%5Bi%5D%5B0%5D = dp%5Bi-1%5D%5B0%5D + s1.charAt(i-1);%0A    %7D%0A    for (int j = 1; j %3C= m; j++) %7B%0A      dp%5B0%5D%5Bj%5D = dp%5B0%5D%5Bj-1%5D + s2.charAt(j-1);%0A    %7D%0A%0A    for (int i = 1; i %3C= n; i++) %7B%0A      for (int j = 1; j %3C= m; j++) %7B%0A        char a = s1.charAt(i-1), b = s2.charAt(j-1);%0A        dp%5Bi%5D%5Bj%5D = dp%5Bi-1%5D%5Bj-1%5D + ((a == b) ? 0 : (a + b)); // match or substitution%0A        dp%5Bi%5D%5Bj%5D = Math.min(dp%5Bi%5D%5Bj%5D, dp%5Bi-1%5D%5Bj%5D + a); // delete from s1%0A        dp%5Bi%5D%5Bj%5D = Math.min(dp%5Bi%5D%5Bj%5D, dp%5Bi%5D%5Bj-1%5D + b); // delete from s2 (insert into s1)%0A      %7D%0A    %7D%0A    return dp%5Bn%5D%5Bm%5D;%0A  %7D%0A%7D%0A

add solution