# java dp solution beats 99%

• ``````public class Solution {
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
if (n == 0 || n > m) return 0;

char[] ss = s.toCharArray(), tt = t.toCharArray();
int[] right = new int[n];
int[] left = new int[n];

int index = 0;
for (int i = 0; i < n;) {
if (tt[i] == ss[index])
right[i++] = index;
index++;
if (index == m && i != n) return 0;
}

index = m - 1;
for (int i = n - 1; i >= 0;) {
if (tt[i] == ss[index])
left[i--] = index;
index--;
}

int[][] record = new int[m][n];
recursive(record, m - 1, n - 1, right, left, ss, tt);

return record[m - 1][n - 1];
}

public void recursive(int[][] record, int i, int j, int[] right, int[] left, char[] ss, char[] tt) {
int bound = Math.min(left[j], i);
for (int k = right[j]; k <= bound; k++) {
if (tt[j] == ss[k]) {
if (j == 0) { record[i][j]++; continue; }

if (record[k - 1][j - 1] == 0) recursive(record, k - 1, j - 1, right, left, ss, tt);
record[i][j] += record[k - 1][j - 1];
}
}
}
}
``````

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