Distinct Subsequences

Distinct Subsequences

30%

Accepted

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

Have you met this question in a real interview? 

Yes

Example

Given S = "rabbbit", T = "rabbit", return 3.

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.

public class Solution {
    /**
     * @param S, T: Two string.
     * @return: Count the number of distinct subsequences
     */
    public int numDistinct(String S, String T) {
        // write your code here
        int[] record = new int[T.length()+1];
        record[0] = 1;
        for(int i = 0; i < S.length(); i++){
            for(int j = T.length(); j >= 1; j--){
                if(S.charAt(i) == T.charAt(j-1)){
                    record[j] += record[j-1];
                }
            }
        }
        return record[T.length()];
    }
}