LeetCode 115. 不同的子序列

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

博客好久没更新了orz…

题目链接

官方给的做法是用动态规划，不过我用的玄学做法也做对了

代码如下：

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;
    }
};

思路

首先找出t中每个字符在s中出现的位置，存到dict里面。

然后对于t，从最后一位开始往前倒序地考虑【从这一位开始，到最后一位，这部分子串】出现在s中的位置有几种可能

最后把所有的可能性累加在一起，就是最终的答案

在累加的过程中，使用sum数组记录后缀和，减少重复计算

第一次提交sum数组爆int了，改成long long就过了

用两组例子来解释一下

第一组样例：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
最后answer = 3+1+1 = 5

第二组样例：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
最后answer = 3