力扣 1055Java

题目描述

给定两个字符串 `A` 和 `B`，返回 `A` 中可能的子序列与 `B` 中相等字符串数。

我们用 `S(A)` 表示 A 的所有字符的集合，而 `s(B)` 是 B 中字符的集合。

当 `A` 的一个子序列能与 `B` 中恰好的一个子序列匹配时，我们认为这是一个好的匹配。

形式上，我们首先用以下方式定义 A 和 B 中的子序列：

- 给定一个字符串 S，一个 S 的子序列是通过从 S 中删除一些（也可能不删除）字符而不更改其余元素的顺序而形成的。例如，"ACE" 是 "ABCDE" 的子序列，但 "AEC" 不是。

我们用以下方式定义一个好的匹配：

- 假设 A 和 B 中分别有相同长度的 n 个字符索引数组 `orderA` 和 `orderB`。
- 如果在 `orderA` 中，第 `i` 个字符出现在在样例中第 `j` 个字符之前（即那些在 `orderA` 中比第 `i` 个字符更早出现的字符的下标在在 `orderB` 中出现的位置全都在第 `j` 个字符之前），那么在 `orderB` 中第 `j` 个字符之后出现的下一个与之匹配的字符需要在 `orderA` 中出现在第 `i + 1` 个字符之后。
- 我们还需要这样的一个保证：在 `orderB` 中要出现的字符必须是从 `s(B)` 中不断地选择至多一次形成的字符串。例如，如果 `B = "xxy"，那么不能选择 "xyy" 或 "yxx" 作为 `B` 自己的子序列。

示例 1:

输入：A = "acd", B = "abdc", 输出: 1
解释：A 中的一个子序列 "acd" 可以通过从 B 中删除 "b" 和 "d" 的方式得到。

示例 2:

输入：A = "db", B = "db", 输出：1
解释：A 中的所有字符与 B 中的每个字符都相等。

示例 3:

输入：A = "aaa", B = "aaa", 输出：3
解释：A 中的每个字符与 B 中的每个字符都相等，因此有 3 种不同的子序列与 B 相等，即 A 本身和空字符串，另外两个找不到 A 中的任何字符的子序列。

提示:

- `1 <= A.length, B.length <= 1000`
- `S(A)` 和 `s(B)` 都只包含小写字符。