Python DP solution, O(n) space, O(m*n) time, 220ms


  • 0
    C

    For dp table, current row only depends on the previous row, so two lists instead of a matrix are enough:

    def numDistinct(self, S, T):
        lt, ls = len(T), len(S)
        if lt > ls or lt == 0:
            return 0
        
        dp = [1] * (ls + 1)
        for i in range(lt):
            new_dp = [0] * (ls + 1)
            for j in range(ls):
                if i <= j:
                    new_dp[j + 1] = new_dp[j] + (T[i] == S[j]) * dp[j]
            dp = new_dp
        return dp[ls]

Log in to reply
 

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