Could someone please clarify this problem to me?
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" count = 3
If I understood correctly, we need to find all distinct subsequences of T and see how many, if any appear in s. How does that equal to 3 in the given example?
Since you can choose two
b from three and there are total of 3 choices,
the first and the second the first and the third the second and the third
so in S we have
so there're totally 3.
I don't think the problem statement is correct: "count the number of distinct subsequences of T in S"
What you really want to count is "the number of distinct subsequences of S equal to T"
Mircea, I agree with you that the statement of this problem is very confusing.
I prefer Jing's explanation, because it makes the definition of "the distinct subsequence of S" very clear.
I give several examples to explain this:
If S=rabb T=ra, there is only one subsequence of S equal to T: ra *.
If S=rabb T=rab, there are two distinct subsequence of S equal to T: ra * b and rab *.
If S=rsabb T=rab, there are two distinct subsequence of S equal to T: r * a * b and r * ab *.
If S=rarab T=ra, there are three distinct subsequence of S equal to T: ra *, * ra *, and r * a *.
Hope this will help others.
Quote from http://www.programcreek.com/2013/01/leetcode-distinct-subsequences-total-java/ :
The problem itself is very difficult to understand. It can be stated like this:
Give a sequence S and T, how many distinct sub sequences from S equals to T?
How do you define "distinct" subsequence? Clearly, the 'distinct' here mean different operation combination, not the final string of subsequence. Otherwise, the result is always 0 or 1.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.