Given a stringSand a stringT, count the number of distinct subsequences ofTinS.

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

Have you met this question in a real interview?

Yes

Example

Given S ="rabbbit", T ="rabbit", return3.

Challenge

Do it in O(n2) time and O(n) memory.

O(n2) memory is also acceptable if you do not know how to optimize memory.

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;

    }

    int len1 = S.size\(\);

    int len2 = T.size\(\);

    int nums\[len1 + 1\]\[len2 + 1\];

    for \(int i = 0; i <= len1; ++i\) {

        nums\[i\]\[0\] = 1; 

    }

    for \(int j = 1; j <=len2; ++j\) {

        nums\[0\]\[j\] = 0;

    }

    for \(int i = 1; i <= len1; ++i\) {

        for \(int j = 1; j <= len2; ++j\) {

            if \(i < j\) {

                nums\[i\]\[j\] = 0;

                continue;

            }

            nums\[i\]\[j\] = nums\[i - 1\]\[j\];

            if \(S\[i - 1\] == T\[j - 1\]\) {

                nums\[i\]\[j\] += nums\[i - 1\]\[j - 1\];

            }

        }

    }

    return nums\[len1\]\[len2\];

}

};