CODEWITHSUNDEEP
python-3.xdynamic-programminglongest-substring
Souvik Ray
Souvik Ray

Reputation: 3038

Longest Common Subsequence program throws a string index out of range error

I have two strings

str1 = "bqdrcvefgh"

str2 = "abcvdefgh"

I want to find the LCS between the two strings.But I am encountering string index out of range exception.This is my code

str1 = "bqdrcvefgh"
str2 = "abcvdefgh"
#taking str1 as column and str2 as row
lis = [[0]*(len(str1)+1) for i in range(len(str2)+1)]

#The first row and first column has default value of 0
for i in range(1,len(str2)+1):
    for j in range(1,len(str1)+1):
        if str2[i]==str1[j]:
            lis[i][j] = lis[i-1][j-1]+1
        else:
            lis[i][j] = max(lis[i][j-1],lis[i-1][j])

#length of the longest LCS
print(lis[len(str2)][len(str1)])

What am I doing wrong?

PS-The correct answer is 7

Upvotes: 0

Views: 452

Answers (1)

Nir Alfasi
Nir Alfasi

Reputation: 53565

Indexes are running from zero till len-1 (it was running from 1 till len inclusive).

Here's the fixed code:

def lcs(str1, str2):    
    #taking str1 as column and str2 as row
    lis = [[0]*(len(str1)) for i in range(len(str2))]
    for i in range(len(str2)):
        for j in range(len(str1)):
            if str2[i]==str1[j]:
                lis[i][j] = lis[i-1][j-1]+1
            else:
                lis[i][j] = max(lis[i][j-1],lis[i-1][j])

    #length of the longest LCS
    print(lis[len(str2)-1][len(str1)-1])

str1 = "bqdrcvefgh"
str2 = "abcvdefgh"    
lcs(str1, str2)  # prints 7

Upvotes: 0

Related Questions