LeetCode 115. 不同的子序列

  • 2021-03-20
  • 2,228
  • 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

 

评论

还没有任何评论,你来说两句吧

发表评论

冀ICP备19026961号