package leetcode;

/**
 * https://leetcode.com/problems/distinct-subsequences/
 */
public class Problem115 {
    public int numDistinct(String s, String t) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem115 prob = new Problem115();
        System.out.println(prob.numDistinct("rabbbit", "rabbit")); // 3
    }
}

@@ -163,201 +163,1030 @@
     
-// TODO%0A        return 0;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem115 prob = new Problem115();%0A        System.out.println(prob.numDistinct(%22rabbbit%22, %22rabbit%22)); // 3
+int%5B%5D%5B%5D memo = new int%5Bs.length() + 1%5D%5Bt.length() + 1%5D;%0A        for (int i = 0; i %3C s.length(); i++) %7B%0A            for (int j = 0; j %3C t.length(); j++) %7B%0A                memo%5Bi%5D%5Bj%5D = -1;%0A            %7D%0A        %7D%0A        return numDistinct(s, t, 0, 0, memo);%0A    %7D%0A%0A    private static int numDistinct(String s, String t, int i, int j, int%5B%5D%5B%5D memo) %7B%0A        if (i %3E= s.length() %7C%7C j %3E= t.length()) %7B%0A            return 0;%0A        %7D%0A        int val = (s.charAt(i) == t.charAt(j)) ? 1 : 0;%0A        int a = numDistinct(s, t, i + 1, j, memo) + val;%0A        int b = numDistinct(s, t, i + 1, j + 1, memo);%0A        int max = Math.max(a, b);%0A        return max;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem115 prob = new Problem115();%0A        System.out.println(prob.numDistinct(%22rabbbit%22, %22rabbit%22)); // 3%0A        System.out.println(prob.numDistinct(%22abc%22, %22def%22)); // 0%0A        System.out.println(prob.numDistinct(%22defaxc%22, %22abc%22)); // 0%0A        System.out.println(prob.numDistinct(%22faxbmcd%22, %22abc%22)); // 1
 %0A   

Update problem 115