public class Solution {

public int numDistinct(String s, String t) {

int[][] cnt = new int[s.length() + 1][t.length() + 1];

//cnt[i][j] = cnt[i - 1][j] if s[i - 1] != t[j - 1];

//cnt[i][j] = cnt[i - 1][j] + cnt[i - 1][j - 1] if s[i - 1] == t[j - 1];

for(int i = 0; i< s.length(); i++) {

cnt[i][0] = 1;

}

for(int i = 1; i <= s.length(); i++) {

for(int j = 1; j <= t.length(); j++) {

if(s.charAt(i - 1) == t.charAt(j - 1)) {

cnt[i][j] = cnt[i - 1][j] + cnt[i - 1][j - 1];

} else {

cnt[i][j] = cnt[i - 1][j];

}

}

}

return cnt[s.length()][t.length()];

// return count(s.toCharArray(), s.length() - 1, t.toCharArray(), t.length() - 1);

}

// we can use only one array to have O(n) space complexity

int dp(String s, String t){

if(s.length() < t.length()) return 0;

int[] res = new int[s.length() + 1];

res[0] = 1;

for(int i = 1; i <= s.length(); i++) {

for(int j = t.length(); j > 0; j--) {

if(s.charAt(i - 1) == t.charAt(j - 1) ) {

res[j] += res[j - 1];

}

}

}

return res[t.length()];

}

// use recursion method, it doesn't work for long strings

int count(char[] s, int sEnd, char[] t, int tEnd) {

if(tEnd < 0 && sEnd >=0) return 1;

if(sEnd < 0) return 0;

if(tEnd == 0 && sEnd == 0 ) {

if(s[sEnd] == t[tEnd]) return 1;

else return 0;

}

int cnt = 0;

if(s[sEnd] == t[tEnd]) {

cnt = count(s, sEnd - 1, t, tEnd) + count(s, sEnd - 1, t, tEnd - 1);

} else {

cnt = count(s, sEnd - 1, t, tEnd);

}

return cnt;

}

}