• Distinct Subsequences

Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.
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"
Return 3.
Solution:
1. public class Solution {
2. public int numDistinct(String s, String t) {
3. int n = s.length(), m = t.length();
4. 5. // dp(i, j) represents the count of S(1...i) and T(1...j)
6. int[][] dp = new int[n + 1][m + 1];
7. 8. for (int i = 0; i <= n; i++)
9. dp[i][0] = 1;
10. 11. for (int i = 1; i <= n; i++) {
12. for (int j = 1; j <= m; j++) {
13. if (s.charAt(i - 1) == t.charAt(j - 1)) {
14. dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
15. } else {
16. dp[i][j] = dp[i - 1][j];
17. }
18. }
19. }
20. 21. return dp[n][m];
22. }
23. }