Python DP for your reference

  • 0
    class Solution:
        # @return an integer
        def numDistinct(self, S, T):
            cache = {}
            for i in range(len(S)+1):
                cache[i, 0] = 1
            for j in range(1, len(T)+1):
                cache[0, j] = 0
            for i in range(1, len(S)+1):
                for j in range(1, len(T)+1):
                    cache[i, j] = cache[i-1, j]
                    if S[i-1] == T[j-1]:
                        cache[i, j] += cache[i-1, j-1]
            return cache[len(S), len(T)]

Log in to reply

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