Easy to understand, Distinct Subsequences DP accepted code


  • 0
    T

    define numDistinct(S,T) is the number of distinct subsequences of S which equals T. The subsequences must start from certain element of S. Then we have
    numDistinct(S,T) = sum{numDistinctStart(S[i:],T)},
    where numDistinctStart(S[i:],T) is the number of subsequence starting from index i, which equals string T. We have:
    numDistinctStart(S[i:],T[j:]) =0, if S[i]!=T[j]
    numDistinctStart(S[i:],T[j:]) = \sum_{k=i+1}^S.size() numDistinctStart(S[k:],T[j+1:]) if S[i]==T[j]

    And we have numDistinctStart(S,T)==0 if S.size()<T.size(), numDistinctStart(S[i:],T[j:])=1 if j==T.size() and S[i]== T[T.size()-1]. The following code is accepted. Maybe the code can be optimized.
    
    class Solution {
    public:
    	/**
    	* @param S, T: Two string.
    	* @return: Count the number of distinct subsequences
    	*/
    	int numDistinct(string &S, string &T) {
    		vector<vector<int>> numDistinctStart(S.size(), vector<int>(T.size(), 0));
    		for (int i = numDistinctStart.size() - 1; i >= 0; i--) {//relation
    			for (int j = numDistinctStart[0].size() - 1; T.size() - j <= S.size() - i&&j>=0; j--) {
    				if (S[i] == T[j]) {
    					if (j+1==T.size()) {
    						numDistinctStart[i][j] += 1;
    					}
    					else {
    						for (int k = i + 1; k < S.size(); k++) {
    							numDistinctStart[i][j] += numDistinctStart[k][j + 1];
    						}
    					}
    				}
    			}
    		}
    		int result = 0;
    		for (int i = 0; i < numDistinctStart.size(); i++) {
    			result += numDistinctStart[i][0];
    		}
    		return result;
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.