Python solution with O(n) space and O(mn) time (10 lines!)


  • 0
    D
    class Solution(object):
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """
        countList = []
        
        len_t = len(t)
        
        for i in range(len_t+1):
            countList.append(0)
        
        countList[0] = 1
        
        for char in s:
            for j in range(len_t-1, -1, -1):
                if countList[j] != 0 and t[j] == char:
                    countList[j+1] += countList[j]
        
        return countList[len_t]

Log in to reply
 

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