Distinct Subsequences

Description:
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).

Example:
Given S = “rabbbit”, T = “rabbit”, return 3.

分析：

  动态规划，关键是如何得到递推关系，可以这样想：设母串的长度为 j，子串的长度为 i，我们要求的就是长度为 i 的子串在长度为 j 的母串中出现的次数，设为dp[i][j]。可以分为下面两种情况：

  1. 若母串的最后一个字符与子串的最后一个字符不同，则长度为 i 的子串在长度为 j 的母串中出现的次数就是母串的前 j - 1 个字符中子串出现的次数，即 dp[i][j] = dp[i][j - 1]。
  2. 若母串的最后一个字符与子串的最后一个字符相同，那么除了前 j - 1 个字符出现字串的次数外，还要加上子串的前 i - 1 个字符在母串的前 j - 1 个字符中出现的次数，即 dp[i][j] = dp[i][j- 1] + dp[i - 1][j - 1]。

注：此题目也可以用一维数组的DP来完成，写出来后更新。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

class Solution {
public:
    /**
    * @param S, T: Two string.
    * @return: Count the number of distinct subsequences
    */
    int numDistinct(string &S, string &T) {
        // write your code here
        // 二维数组
        if (S.size() < T.size()) return 0;
        if (T.size() == 0) return 1;
        vector<vector<int> > dp(T.size() + 1, vector<int>(S.size() + 1, 0));
        for (int i = 0; i < S.size(); i++) {
            dp[0][i] = 1;
        }

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

        return dp[T.size()][S.size()];
    }
};

滚动数组：

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:    
    /**
     * @param S, T: Two string.
     * @return: Count the number of distinct subsequences
     */
    int numDistinct(string &S, string &T) {
        // write your code here
        if (S.size() < T.size()) return 0;
        vector<int> dp(T.size() + 1, 0);
        dp[0] = 1;

        for (int i = 1; i <= T.size(); i++) {
            dp[i] = 0;
        }
        for (int i = 1; i <= S.size(); i++) {
            for (int j = T.size(); j >= 1; j--) {
                if (S[i - 1] == T[j - 1]) {
                    dp[j] += dp[j - 1];
                }
            }
        }

        return dp[T.size()];
    }
};