Task clarification


  • 75
    P

    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?


  • 6
    P

    Since you can choose two b from three and there are total of 3 choices,
    i.e.,

    the first and the second
    the first and the third
    the second and the third

  • 86
    J

    I think what the questions means is try to find subsequences in S, such that the subsequence is same as T.
    so in S we have


    rabbit=T

    rab
    bit=T

    ra*bbit=T

    so there're totally 3.


  • 54
    M

    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"


  • 3
    W

    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.


  • 0
    P

    So, if S is "rabbbbit" and T is "rabbit", the expected result would be 6?


  • 0
    S

    yes
    ra#bb#it
    ra##bbit
    rabb##it
    rab#b#it
    rab##bit
    ra#b#bit
    6 totally


  • 0
    D

    That's very helpful, thanks!


  • 0
    M

    Typo in your comment. The third example is rabb*it=T


  • 7

    I can't believe that the statements remain unmodified.


  • 3
    C

    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.


  • 0
    Y

    It also took me some mins to understand the problem


  • 0

    @jedihy Very confusing, huh?


  • 0
    W

    @mircea I have totally same thought of yours


Log in to reply
 

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