Space O(mn) and O(n) Python solutions


  • 1

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

    When I read the question again, I found the phrase cited may be wrong. The question asks us to find distinct subsequence of S == T. If we count the number of distinct subsequences of T in S and S = "rabbbit" and T = "rabbit", then "r" is a subsequence of T and will be counted too. That is obviously not what we want.

    Then, we can write the relation which is very similar to LCS. I just remove one state transition from LCS and sum them up. Because T could not be subsequence so dp[i][j] can only come from dp[i - 1][j - 1] and dp[i - 1][j - 1]. dp[i][j - 1] cannot be counted because it will lead to miss some letters in T (becoming subsequence).

    Recurrence relation:

    dp[i][j] = dp[i - 1][j] +( dp[i - 1][j - 1] if s[i - 1] == s[j - 1])

    class Solution(object):
        def numDistinct(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: int
            """
            dp = [[0 for j in xrange(0, len(t) + 1)] for i in xrange(0, len(s) + 1)]
            for j in xrange(1, len(t) + 1):
                dp[0][j] = 0
            for i in xrange(1, len(s) + 1):
                dp[i][0] = 1
    
            dp[0][0] = 1
    
            for i in xrange(1, len(s) + 1):
                for j in xrange(1, len(t) + 1):
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * (s[i - 1] == t[j - 1])
    
            return dp[-1][-1]
    

    Space optimization:
    The states are only from top and left-top. Thus, 1-D array is enough and uses some temp variables to roll the array all the way down.

    class Solution(object):
        def numDistinct(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: int
            """
            dp = [0 for _ in xrange(0, len(t) + 1)]
            dp[0] = 1
            for i in xrange(1, len(s) + 1):
                pre = dp[0]
                for j in xrange(1, len(t) + 1):
                    tmp = dp[j]
                    dp[j] = dp[j] + pre * (s[i - 1] == t[j - 1])
                    pre = tmp
            return dp[-1]
    

  • 1
    S

    It can be further improved, if unrelated characters are removed.
    And the multiply of pre and comparison result can be replaced by addition, if the loop is looped from end to the start. Here is my code. :)

    class Solution(object):
        def numDistinct(self, s, t):
            pat_chars = set(t)
            s = [c for c in s if c in pat_chars]
            n, m = len(s), len(t)
            dp = [1] + [0] * m
            for i in range(1, n+1):
                for j in range(min(i+1,m), 0, -1):
                    if s[i-1] == t[j-1]:
                        dp[j] += dp[j-1]
            return dp[m]
    

  • 0

    @ShuiHan Brilliant idea!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.