Skip to content

Latest commit

 

History

History
194 lines (138 loc) · 3.87 KB

0115._Distinct_Subsequences.md

File metadata and controls

194 lines (138 loc) · 3.87 KB

115. Distinct Subsequences

难度: Hard

刷题内容

原题连接

内容描述

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:

As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
Example 2:

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:

As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

解题方案

思路 1 - 时间复杂度: O(2^m)- 空间复杂度: O(1)******

递归，超时

class Solution:
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """
        if len(t) == 0:
            return 1
        if len(s) == 0:
            return 0
        if s[-1] == t[-1]:
            return self.numDistinct(s[:-1], t[:-1]) + self.numDistinct(s[:-1], t)
        else:
            return self.numDistinct(s[:-1], t)

存下中间状态，还是超时

class Solution:
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """ 
        if len(t) == 0:
            return 1
        if len(s) == 0:
            return 0
        option1 = self.numDistinct(s[:-1], t)
        if s[-1] == t[-1]:
            option2 = self.numDistinct(s[:-1], t[:-1])
            return option2 + option1
        else:
            return option1

思路 2 - 时间复杂度: O(m * n)- 空间复杂度: O(m * n)******

DP

dp[i][j]代表s的前i个字符中有多少个subsequence等于t的前j个字符

状态转移：

  • 如果当前字符s[i-1] != t[j-1]，说明即使我们没有s当前的字符也是一样 --> dp[i][j] = dp[i-1][j]
  • 如果当前字符s[i-1] == t[j-1]，说明现在有两种可能的组合方式：
    • 一是我们s和t的当前字符都不要了，即dp[i-1][j-1]有多少种（All substrings without last characters in both.）， 我们后面加上当前字符，就有多少种
    • 二是我们单单不要s的当前字符（ All substrings without last character in S ）有多少种

beats 73.75%

class Solution:
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """     
        m, n = len(s), len(t)
        if n > m:
            return 0
        dp = [[0] * (n+1) for i in range(m+1)]
        for i in range(m+1):
            dp[i][0] = 1
        for i in range(1, m+1):
            for j in range(1, n+1):
                if s[i-1] != t[j-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
        return dp[-1][-1]

思路 3 - 时间复杂度: O(m * n)- 空间复杂度: O(n)******

优化空间

beats 77.25%

class Solution:
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """   
        m, n = len(s), len(t)
        if n > m:
            return 0
        dp = [0] * (n+1)
        dp[0] = 1
        for i in range(1, m+1):
            tmp = dp[:]
            for j in range(1, n+1):
                if s[i-1] != t[j-1]:
                    dp[j] = tmp[j]
                else:
                    dp[j] = tmp[j] + tmp[j-1]
        return dp[-1]