21dk04

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

English description is not available for the problem. Please switch to Chinese.

numDistinct

不同的子序列

String

Dynamic Programming

给定一个字符串 <code>s</code> 和一个字符串 <code>t</code> ，计算在 <code>s</code> 的子序列中 <code>t</code> 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，<code>&quot;ACE&quot;</code> 是 <code>&quot;ABCDE&quot;</code> 的一个子序列，而 <code>&quot;AEC&quot;</code> 不是）

题目数据保证答案符合 32 位带符号整数范围。

&nbsp;

示例 1：

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

示例 2：

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

&nbsp;

提示：

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

&nbsp;

<meta charset="UTF-8" />注意：本题与主站 115 题相同： <a href="https://leetcode-cn.com/problems/distinct-subsequences/">https://leetcode-cn.com/problems/distinct-subsequences/</a>

&nbsp;