LeetCode Q115 Distinct Subsequences (hard)

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

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

Solution:
Finally, I thoroughly solved a DP totally by myself. 

Usually, the question about two strings like this should be solved by DP using a M x N table with time complexity equals O(MN).

Let's have a table H to save all intermediate results. Entry H[i][j] represents the number of distinct subsequences  between S[0:i] and T[0:j].

Following is the transition equation:

i. If S[i]!=T[j], then H[i][j]=H[i-1][j].

ii. If S[i]==T[j], then H[i][j]=H[i-1][j-1]+H[i-1][j].

So, to solve H[i][j], we basically, need to get last row and previous column solved first, which in our problem can be do by two loops and solved rows by rows.

	class Solution {
	public:
	int numDistinct(string s, string t) {
	vector<vector<int> > H(s.length()+1, vector<int> (t.length()+1, 0));
	for(int i=0; i<=s.length(); i++)
	H[i][0]=1;
	for(int i=1; i<=s.length(); i++){
	for(int j=1; j<=t.length(); j++){
	H[i][j]=s[i-1]==t[j-1]?H[i-1][j-1]+H[i-1][j]:H[i-1][j];
	}
	}
	return H[s.length()][t.length()];
	}
	};

view raw Q115DistinctSubsequences.cpp hosted with ❤ by GitHub