Clever Geek Handbook

Number of distinct subsequences

There is a problem with the liket code: different subsequences.

Given string S and string T, count the number of distinct subsequences of T in S. The subsequence of a string is a new string that is formed from the original string by removing some (maybe none) characters without violating the relative positions of the remaining characters. (ie "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here's an example: S = "rabbit", T = "rabbit" Return 3.

My questions:

Here I don't understand what is the point of "counting the number of distinct subsequences of T in S" I think that "r", "ra", "b" rab "," rabt ", etc. are all subsequences of T, and they are also in S. But the answer gives the answer "3." So I must have misunderstood the problem, can someone explain it to me? Just give me some typical examples and explanations in order, and don't tell me how to solve them I hope to do this as an exercise. Thanks in advance

+3


source to share


2 answers


You can get T = "rabbit" from S = "rabbit" by removing either the first, second, or third "b" in S. Therefore, there are 3 possible choices.



0


source


I think you have misunderstood this question. Count the number of distinct subsequences of T in S, means how many unique occurrences of T (rabbit) there are in S (rabbit).

Answer three:

( bold letter is deleted)

ra b bb i t == rabbit



rab b b i t == rabbit

rabb b i t == rabbit

Cm? Three different subsequences of the word "rabbit" have taken the string "rabbit". Each time every character was removed.

0


source






More articles:


All Articles