Given a string S and a string T, count the number of distinct subsequences of S which equals T.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,"ACE"is a subsequence of"ABCDE"while"AEC"is not).
Here is an example:
S="rabbbit",T="rabbit"
Return3.
2. Implementation
(1) DP
public class Solution {
public int numDistinct(String s, String t) {
int m = t.length();
int n = s.length();
// dp[i][j] is the number of distinct subsequence in S.substring(0, j) that are equal to T.substring(0, i)
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// for the first row, empty string(row) is the subsequence of any string
if (i == 0) {
dp[i][j] = 1;
}
// for the first column, empty string(column) has no subsequence
else if (j == 0) {
dp[i][j] = 0;
}
// if t[i - 1] == s[j - 1], two options:
// (1) All subsequence without last character in S
// (1) All subsequence without last character in both
else if (t.charAt(i - 1) == s.charAt(j - 1)) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
}
// If last characters don't match, the number of distinct subsequences is the same
// subsequences without the last character in S
else {
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[m][n];
}
}