LC-0115 Hard LeetCode

115. Distinct Subsequences

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 50% Topics: String, Dynamic Programming

Reading material

Strings 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n^2)
# Space: O(n)

class Solution(object):
    # @return an integer
    def numDistinct(self, S, T):
        ways = [0 for _ in xrange(len(T) + 1)]
        ways[0] = 1
        for S_char in S:
            for j, T_char in reversed(list(enumerate(T))):
                if S_char == T_char:
                    ways[j + 1] += ways[j]
        return ways[len(T)]

Solution from kamyu104/LeetCode-Solutions · MIT