Участник:Evgin/distinct subsequences

Ссылки сюда (1) →

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

Python3

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [0] * (len(t) + 1)
        dp[0] = 1
        indices = {}
        for i, c in enumerate(t):
            if c not in indices:
                indices[c] = []
            indices[c].append(i + 1)
        for v in indices.values():
            v.reverse()
        for c in s:
            if c in indices:
                for i in indices[c]:
                    dp[i] += dp[i - 1]
        return dp[len(t)]