@@ -0,0 +1,1142 @@
+package com.interview.dynamic;%0A%0A/**%0A * Date 03/20/2016%0A * @author Tushar Roy%0A *%0A * Given a string S and a string T, count the number of distinct subsequences of T in S.%0A *%0A * Time complexity O(n%5E2)%0A * Space complexity O(n%5E2)%0A *%0A * https://leetcode.com/problems/distinct-subsequences/%0A */%0Apublic class DistinctSubsequence %7B%0A    public int numDistinct(String s, String t) %7B%0A        if (s.length() == 0 %7C%7C t.length() == 0) %7B%0A            return 0;%0A        %7D%0A        int%5B%5D%5B%5D T = new int%5Bt.length() + 1%5D%5Bs.length() + 1%5D;%0A        for (int i = 0; i %3C T%5B0%5D.length; i++) %7B%0A            T%5B0%5D%5Bi%5D = 1;%0A        %7D%0A        for (int i = 1; i %3C T.length; i++) %7B%0A            for (int j = 1; j %3C T%5B0%5D.length; j++) %7B%0A                if (s.charAt(j - 1) == t.charAt(i - 1)) %7B%0A                    T%5Bi%5D%5Bj%5D = T%5Bi-1%5D%5Bj-1%5D + T%5Bi%5D%5Bj-1%5D;%0A                %7D else %7B%0A                    T%5Bi%5D%5Bj%5D = T%5Bi%5D%5Bj-1%5D;%0A                %7D%0A            %7D%0A        %7D%0A        return T%5Bt.length()%5D%5Bs.length()%5D;%0A    %7D%0A%0A    public static void main(String args%5B%5D) %7B%0A        DistinctSubsequence ds = new DistinctSubsequence();%0A        System.out.println(ds.numDistinct(%22abdacgblc%22, %22abc%22));%0A    %7D%0A%7D%0A

Count distinct subsequences