number of distinct subsequence
There is a leetcode problem: distinct subsequences.
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.
My questions:
Here, I don't understand what is the meaning of "count the number of distinct subsequences of T in S" I think "r", "ra","b" rab", "rabt" etc. are all subsequences of T, and they are also in S. But the return gives answer "3". So, I must have misunderstood the problem, could anyone explain it to me? Just giving me some more typical examples and explanations is OK and don't tell me how to solve it, I hope to do it as an exercise. Thanks in advance
通过删除S中的第一个，第二个或第三个“b”，可以从S =“rabbbit”中获得T =“rabbit”。因此，可能的变体的数量是3。
I think you misunderstood the question. Count the number of distinct sub-sequences of T in S means how many unique appearances of T (rabbit) are there in S (rabbbit).
The answer is three:
(The bold letter being the deleted one)
ra b bbit == rabbit
rab b bit == rabbit
rabb b it == rabbit
See? Three distinct sub-sequences of the word "rabbit" taken the string "rabbbit". A different character was deleted each time.
链接地址: http://www.djcxy.com/p/61512.html下一篇: 不同子序列的数量