FilesExpand file tree

 patch-2

/

longest_common_subsequence.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

37 lines (32 loc) · 1.06 KB

 patch-2

/

longest_common_subsequence.py

Copy path

Top

File metadata and controls

• Code
• Blame

37 lines (32 loc) · 1.06 KB

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

34

35

36

37

"""

LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them.

A subsequence is a sequence that appears in the same relative order, but not necessarily continious.

Example:"abc", "abg" are subsequences of "abcdefgh".

"""

from __future__ import print_function

try:

xrange # Python 2

except NameError:

xrange = range # Python 3

def lcs_dp(x, y):

# find the length of strings

m = len(x)

n = len(y)

# declaring the array for storing the dp values

L = [[None] * (n + 1) for i in xrange(m + 1)]

seq = []

for i in range(m + 1):

for j in range(n + 1):

if i == 0 or j == 0:

L[i][j] = 0

elif x[i - 1] == y[ j - 1]:

L[i][j] = L[i - 1][j - 1] + 1

seq.append(x[i -1])

else:

L[i][j] = max(L[i - 1][j], L[i][j - 1])

# L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]

return L[m][n], seq

if __name__=='__main__':

x = 'AGGTAB'

y = 'GXTXAYB'

print(lcs_dp(x, y))