算法: 不同的子序列115. Distinct Subsequences
Given two strings s and t, return the number of distinct subsequences of s which equals t.
A string’s subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters’ relative positions. (i.e., “ACE” is a subsequence of “ABCDE” while “AEC” is not).
The test cases are generated so that the answer fits on a 32-bit signed integer.
Example 1:
Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
ra_bbit
rab_bit
rabb_it
Example 2:
Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
ba_g___
ba____g
b____ag
__b__ag
____bag
Constraints:
1 <= s.length,t.length <= 1000- s and t consist of English letters.
动态规划解法
想法如下：
- 我们将构建一个数组dp，其中
dp[i+1][j+1]表示S[0..j]包含T[0..i]多次不同的子序列。因此结果将是dp[T.length()][S.length()]。 - 我们可以逐行构建这个数组：
- 第一行必须填充 1。这是因为空字符串是任何字符串的子序列，但只有 1 次。所以
dp[0][j] = 1对于每个j. 因此，这样我们不仅使我们的生活更轻松，而且如果T是空字符串，我们还返回正确的值。 - 除了第一行，每一行的第一列必须是 0。这是因为空字符串不能包含非空字符串作为子字符串——数组的第一项：
dp[0][0] = 1，因为空字符串包含空字符串 1 次.
所以矩阵看起来像这样：
S 0123....j
T +----------+
|1111111111|
0 |0 |
1 |0 |
2 |0 |
. |0 |
. |0 |
i |0 |
从这里我们可以轻松地填充整个网格：对于 each (x, y)，我们检查是否S[x] == T[y]添加了前一项和前一行中的前一项，否则我们复制同一行中的前一项。原因很简单：
- 如果 S 中的当前字符不等于当前字符 T，那么我们将拥有与没有新字符时相同数量的不同子序列。
- 如果 S 中的当前字符等于当前字符 T，则子序列的不同数量：我们之前拥有的数量加上我们拥有的具有较短 T 和较短 S 的不同子序列数量。
一个例子：
S: [acdabefbc]和T: [ab]
首先我们检查a：
* *
S = [acdabefbc]
mem[1] = [0111222222]
然后我们检查ab：
* * ]
S = [acdabefbc]
mem[1] = [0111222222]
mem[2] = [0000022244]
结果是 4，因为不同的子序列是：
S = [a b ]
S = [a b ]
S = [ ab ]
S = [ a b ]
见Java代码：
class Solution {
public int numDistinct(String s, String t) {
int slen = s.length();
int tlen = t.length();
char[] schar = s.toCharArray();
char[] tchar = t.toCharArray();
int[][] dp = new int[tlen + 1][slen + 1];
for (int c = 0; c <= slen; c++)
dp[0][c] = 1;
for (int r = 0; r < tlen; r++) {
for (int c = 0; c < slen; c++) {
if (tchar[r] == schar[c]) {
dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c];
} else {
dp[r + 1][c + 1] = dp[r + 1][c];
}
}
}
return dp[tlen][slen];
}
}
参考
https://leetcode.com/problems/distinct-subsequences/discuss/37327/Easy-to-understand-DP-in-Java
