# Distinct Subsequences

March 20, 2021 Given two strings s and t, return the number of distinct subsequences of s which equals t.

Example:

Input: s = "babgbag", t = "bag"
Output: 5

As shown below, there are 5 ways you can generate "bag" from s.

babgbag * babgbag * babgbag * babgbag * babgbag

## Code

// s: babgbag -> iterated by pointer j
// t: bag     -> iterated by pointer i

public int numDistinct(String s, String t) {
int S = s.length(), T = t.length();

int[][] dp = new int[T + 1][S + 1];

for (int j = 0; j <= S; j++) {
dp[j] = 1;  }

for (int i = 1; i <= T; i++) {
for (int j = 1; j <= S; j++) {
if (s.charAt(j - 1) == t.charAt(i - 1)) {
dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];      } else {
dp[i][j] = dp[i][j - 1];      }
}
}

return dp[S][T];
}

## State transition

Fill in the DP table row by row. When dealing with a row, assume t (the shorter string) is fixed and s is increasing in character.

Try clicking on different values to show how they are calculated.

""babgbag
""11111111
b01122333
a00111144
g00001115

## Reference

Easy to understand DP in Java