distinct-subsequences

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given two strings s and t, return the number of distinct subsequences of s which equals t.

The test cases are generated so that the answer fits on a 32-bit signed integer.

&nbsp;
Example 1:

<pre>
Input: s = &quot;rabbbit&quot;, t = &quot;rabbit&quot;
Output: 3
Explanation:
As shown below, there are 3 ways you can generate &quot;rabbit&quot; from s.
<code>rabbbit</code>
<code>rabbbit</code>
<code>rabbbit</code>
</pre>

Example 2:

<pre>
Input: s = &quot;babgbag&quot;, t = &quot;bag&quot;
Output: 5
Explanation:
As shown below, there are 5 ways you can generate &quot;bag&quot; from s.
<code>babgbag</code>
<code>babgbag</code>
<code>babgbag</code>
<code>babgbag</code>
<code>babgbag</code></pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length, t.length &lt;= 1000</code></li>
	<li><code>s</code> and <code>t</code> consist of English letters.</li>
</ul>

numDistinct

Distinct Subsequences

Number of Unique Good Subsequences

number-of-unique-good-subsequences

不同的好子序列数目

String

Dynamic Programming

给你两个字符串 <code>s</code> 和 <code>t</code> ，统计并返回在 <code>s</code> 的 子序列 中 <code>t</code> 出现的个数。

测试用例保证结果在 32 位有符号整数范围内。

&nbsp;

示例&nbsp;1：

<pre>
输入：s = "rabbbit", t = "rabbit"<code>
输出</code>：<code>3
</code>解释：
如下所示, 有 3 种可以从 s 中得到 <code>"rabbit" 的方案</code>。
<code>rabbbit</code>
<code>rabbbit</code>
<code>rabbbit</code></pre>

示例&nbsp;2：

<pre>
输入：s = "babgbag", t = "bag"
<code>输出</code>：<code>5
</code>解释：
如下所示, 有 5 种可以从 s 中得到 <code>"bag" 的方案</code>。 
<code>babgbag</code>
<code>babgbag</code>
<code>babgbag</code>
<code>babgbag</code>
<code>babgbag</code>
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length, t.length &lt;= 1000</code></li>
	<li><code>s</code> 和 <code>t</code> 由英文字母组成</li>
</ul>