# Concise JAVA solution based on DP

• Explanation

At first, I tried memorized DFS solution, but got stack overflow with the last large case. So then I was thinking about the non-recursive solution with DP, which is actually a bottom up memorized DFS solution without using stack.

DP Solution:

``````public static int numDistinct(String s, String t) {
int dp[][] = new int[s.length()+1][t.length()+1]; //dp[i][j]: number of the sequences for i long s and j long t
for (int i = 0; i < s.length(); i++)
dp[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))// index = length - 1
//dp[i-1][j]  : don't take s[i-2]
//dp[i-1][j-1]: take s[i-2]
dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
else
dp[i][j] = dp[i-1][j];
}
}
return dp[s.length()][t.length()];
}
``````

DFS Solution: (Stack Overflow)

`````` int slen, tlen;
int nums[][];
public int numDistinct(String s, String t) {
slen = s.length(); tlen = t.length();
nums = new int[slen][tlen];
for (int i = 0; i < slen; i++)
Arrays.fill(nums[i], -1);
return DFS(0, 0, s.toCharArray(), t.toCharArray(), 0, 0);
}

int DFS(int curLen, int si, char[] s, char[] t, int ti, int count) {
if (si > slen - 1 || ti > tlen - 1 || curLen == tlen) {
if (curLen == tlen)
count++;
return count;
}
if (nums[si][ti] != -1) return nums[si][ti];
if (s[si] == t[ti]) count += DFS(curLen + 1, si + 1, s, t, ti + 1, 0);// Take si char
count += DFS(curLen, si + 1, s, t, ti, 0);// Don't take si char
nums[si][ti] = count;
return count;
}``````

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