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

  • 0
    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[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.