FilesExpand file tree

 master

/

subsequence.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

33 lines (27 loc) · 845 Bytes

 master

/

subsequence.py

Copy path

Top

File metadata and controls

• Code
• Blame

33 lines (27 loc) · 845 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

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

cache = {}

def dp_alignment(s1, s2):

if len(s1) == 0 or len(s2) == 0:

return 0

max_comment = 0

if (s1, s2) in cache:

return cache[(s1, s2)]

if s1[0] == s2[0]:

max_comment = dp_alignment(s1[1:], s2[1:]) + 1

cache[(s1, s2)] = max_comment

return max_comment

else:

max_comment = max(dp_alignment(s1, s2[1:]), dp_alignment(s1[1:], s2))

cache[(s1, s2)] = max_comment

return max_comment

if __name__ == '__main__':

string1 = 'nematode knowledge'

string2 = 'empty bottle'

comment = dp_alignment(string1, string2)

print(cache)

print(comment)

# count = 0

# for element in cache:

# if cache[element] > count:

# count = cache[element]

# max_subsequence = element

# print(max_subsequence)