# LeetCode 115. 不同的子序列

• 2021-03-20
• 1,933
• 0
• 0

## 代码如下：

``````class Solution {
public:
map<char, set<int> > letter;
vector<set<int> > dict;
long long place[1005], sum[1005] = { 0 };
int numDistinct(string s, string t) {
int lens = s.length();
int lent = t.length();
for (int i = 0; i < lens; i++) {
letter[s[i]].insert(i);
}
for (int i = 0; i < lent; i++) {
dict.emplace_back(letter[t[i]]);
}
for (int i = lent - 1; i >= 0; i--) {
if (i == lent-1) {
for (auto wh : dict[i]) {
place[wh] = 1;
}
} else {
for (auto wh : dict[i]) {
place[wh] = sum[wh];
}
}
for (int j = lens - 2; j >= 0; j--) {
sum[j] = sum[j + 1] + (dict[i].count(j + 1) ? place[j + 1] : 0);
}
}
long long ans = 0;
for (auto e : dict[0]) {
ans += place[e];
}

return ans;
}
};
``````

## 用两组例子来解释一下

### 第一组样例：s = “babgbag”, t = “bag”

```part1：t中的每个字符可能出现在s中的位置（0-6是s的index）
b   0   2   4
a     1       5
g         3     6
dict[0] = {0, 2, 4}
dict[1] = {1, 5}
dict[2] = {3, 6}

part2：考虑组合的可能性
g: （g出现在位置3有1种可能，位置6有一种可能）
place[3] = 1
place[6] = 1
ag: （ag出现在位置1有[1-3]和[1-6] 2种可能，以此类推）
place[1] = place[3] + place[6] = 2
place[5] = place[6] = 1
bag:
place[0] = place[1] + place[5] = 3
place[2] = place[5] = 1
place[4] = place[5] = 1

### 第二组样例：s = “rabbbat”, t = “rabbat”

```part1：
r   0
a     1       5
b       2 3 4
b       2 3 4
a     1       5
t               6
dict[0] = {0}
dict[1] = {1, 5}
dict[2] = {2, 3, 4}
dict[3] = {2, 3, 4}
dict[4] = {1, 5}
dict[5] = {6}

part2：
t:
place[6] = 1
at:
place[1] = place[6] = 1
place[5] = place[6] = 1
bat:
place[2] = place[5] = 1
place[3] = place[5] = 1
place[4] = place[5] = 1
bbat:
（需要注意，更新place的时候，要从前往后更新。先更新place[4]=0再更新place[3]=place[4]的话数据就被覆盖掉了）
place[2] = place[3+4] = 2
place[3] = place[4] = 1
place[4] = 0
abbat:
place[1] = place[2+3+4] = 3
place[5] = 0
rabbat:
place[0] = place[1+5] = 3