FilesExpand file tree

master

/

distinct-subsequences.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

14 lines (12 loc) · 373 Bytes

master

/

distinct-subsequences.py

Copy path

Top

File metadata and controls

• Code
• Blame

14 lines (12 loc) · 373 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

# 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)]