【leetcode】940. Distinct Subsequences II

淩亂°似流年 2022-01-10 06:09 190阅读 0赞

**题目如下：**

> Given a string `S`, count the number of distinct, non-empty subsequences of `S` .
> 
> Since the result may be large, return the answer modulo `10^9 + 7`.
> 
>  
> 
> Example 1:
> 
>     Input: "abc"
>     Output: 7 Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".
> 
> Example 2:
> 
>     Input: "aba"
>     Output: 6 Explanation: The 6 distinct subsequences are "a", "b", "ab", "ba", "aa" and "aba".
> 
> Example 3:
> 
>     Input: "aaa"
>     Output: 3 Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".

**解题思路：**记dp\[i\]为以S\[i\]元素结尾可以组成的子串的个数，很显然dp\[0\] = 1。显然dp\[i\]的前一个元素可以是dp\[0\] ~ dp\[i-1\]中的任何一个，那么应该有dp\[i\] = dp\[0\] + dp\[1\] +...dp\[i-1\]。这是对于元素没有重复的情况。假设S\[j\]是S\[0-i\]中与S\[i\]下标最接近的元素并且有S\[i\] = S\[j\]，那么在以S\[i\]结尾的子串中，前一个元素是在S\[0\]~S\[j-1\]中的任何一个，都会和以S\[j\]结尾的子串中并且前一个元素是在S\[0\]~S\[j-1\]中的任何一个重复，因此这种情况下dp\[i\] = dp\[j\]+dp\[j+1\] + ... dp\[i-1\]。最后，返回的结果应该为sum(dp）。

**代码如下：**

class Solution(object):
        def distinctSubseqII(self, S):
            """
            :type S: str
            :rtype: int
            """
            dp = [1] * len(S)
            for i in range(1,len(S)):
                for j in range(i-1,-1,-1):
                    if S[i] != S[j]:
                        dp[i] += dp[j]
                    else:
                        dp[i] += dp[j]
                        dp[i] -= 1
                        break
            #print dp
            return sum(dp) % (pow(10,9) + 7)

转载于:https://www.cnblogs.com/seyjs/p/10412749.html