Участник:S1td1kov/DistinctSubsequences

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/distinct-subsequences/

 
//follow my github https://github.com/RusS1103/Leetcode
 
const int ZERO = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}();
 
class Solution {
public:
    int numDistinct(string s, string t) 
    {
        vector<long long> mem(t.size()+1, 0);
        mem[0] = 1;
        for (auto s_c : s)
        {
            for (int i = t.size() - 1; i >= 0; --i)
            {
                if (t[i] == s_c) mem[i+1] += mem[i];
            }
        }
        return *mem.rbegin();
    }
};