# Java DFS solution beats 99%

• Unlike most most DP solutions, I have figured out a solution using DFS with a memo(or is this a top-down DP with memo? I am not sure..)
This Java solution beats 99% of the acceptances.

``````public static int numDistinct(String s, String t) {
if(s.length()<t.length()) return 0;
int rs = checkNext(t.toCharArray(),0,
s.toCharArray(),0,new int[t.length()][s.length()]);
return rs<0?0:rs;
}

private static int checkNext(char[] t,int tarindex,char[] s,int begin,
int[][] memo){
// flags in the memo: 0 undecided, -1 not match(return directly)
// other integers represent the numbers of subsequences.
if(tarindex==t.length) return 1;
if(memo[tarindex][begin]!=0) return memo[tarindex][begin];
int count = 0,remain = t.length-tarindex;
for(int i=begin;i<=s.length-remain;i++){
if(s[i]==t[tarindex]){
int rs = checkNext(t,tarindex+1,s,i+1,memo);
if(rs!=-1) count+=rs;
else break; // no more subsequences, stop checking
}
}
count = count==0?-1:count;
memo[tarindex][begin] = count;
return count;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.