algorithm - 不同子序列的数量

Question

有一个 leetcode 问题：不同的子序列。

给定一个字符串 S 和一个字符串 T，计算 S 中 T 的不同子序列的数量。一个字符串的子序列是一个新的字符串，它是从原始字符串中删除一些（可以是无）字符而不干扰其余字符的相对位置。（即，“ACE”是“ABCDE”的子序列，而“AEC”不是）。

下面是一个例子：S = "rabbbit", T = "rabbit" 返回 3。

---

我的问题：

在这里，我不明白“计算S中T的不同子序列的数量”是什么意思 我认为“r”，“ra”，“b”rab”，“rabt”等都是T的子序列，而且它们也在S中。但是返回给出的答案是“3”。所以，我一定是误解了这个问题，有人能给我解释一下吗？只是给我一些更典型的例子和解释就可以了，不要告诉我如何解决它，我希望将其作为练习。在此先感谢

Answer 1

您可以通过删除 S 中的第一个、第二个或第三个“b”从 S="rabbbit" 中获得 T="rabbit"。因此，可能的变体数量为 3。

Answer 2

我想你误解了这个问题。计算 S 中 T 的不同子序列的数量意味着T（兔子）在 S（兔子）中有多少个独特的出现。

答案是三个：

（粗体字为删除的那个）

ra b bbit == 兔子

rab b bit == 兔子

rabb b it == 兔子

看？单词“rabbit”的三个不同子序列采用字符串“rabbbit”。每次删除不同的字符。