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;
}
}
