Algorithm

LintCode/Distinct Subsequences

Problem Summary

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

Solution

The problem is actually about finding the number of ways to delete some (can be none) of the characters of S such that the remaining string is the same with T.

We can use dynamic programming to solve this problem.

First, let f[i,j] be the number of distinct ways to delete some characters from S[1]S[2]…S[i] such that the remaining string is the same with T[0]T[1]T[2]…T[j]. So we have

f[i,j] = f[i-1,j] , if j ≤ i && S[i] != T[j]
f[i,j] = f[i-1,j] + f[i-1,j-1] , if j ≤ i && S[i] == T[j]

Notice that f[i,j] only depends on f[i-1,j] and f[i-1,j-1]. We can reduce space complexity using f[j] instead of f[i,j]. If S[i] != T[j], there is no need to change the value of f[j]. If S[i] == T[j], we let f[j] += f[j-1]. The f[j-1] here is actually f[i-1,j-1], so we need to enumerate j from min(i,m) down to 1.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    /*
     * @param : A string
     * @param : A string
     * @return: Count the number of distinct subsequences
     */
    int numDistinct(string S, string T) {
    	int n = S.length(), m = T.length();
        int f[m+2];
        memset(f,0,sizeof(f));
        f[0] = 1;
        for (int i = 1; i <= n; ++i)
            for (int j = min(m,i); j>= 1; --j)
                if (S[i-1] == T[j-1])
                    f[j] += f[j-1];
		return f[m];
    }
};