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