Участник:Evgin/distinct subsequences
Материал из DISCOPAL
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)]