【leetcode】940. Distinct Subsequences II

题目如下：

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)

巴特西

【leetcode】940. Distinct Subsequences II

最新文章

热门文章