High execution time of LCS length program in Python2

Question

I was trying to solve the Longest Common Subsequence problem on a HackerRank exercise. It's quite simple and straightforward, just print out the length of the LCS. I submitted this code:

s1 = raw_input()
s2 = raw_input()

lcs = [[0 for j in xrange(len(s2)+1)] for i in xrange(len(s1)+1)]
for i, x in enumerate(s1):
    for j, y in enumerate(s2):
        if x == y:
            lcs[i+1][j+1] = lcs[i][j] + 1
        else:
            lcs[i+1][j+1] = max(lcs[i+1][j], lcs[i][j+1])

print lcs[-1][-1]

I think the logic is fine. The maximum string length is 5000. The problem is with the execution time. Some test cases take more than 10 seconds and the program terminates.

Answer 1

That looks like a classic LCS solution to me.

If all you want is to read the bottom-right element of the tableau, you don't actually have to store the entire matrix: all you need to keep is the most recent row. That could save you a few megabytes of memory — I don't know how much processing time that would save, though.

To initialize the arrays, you can use the * operator instead of a list comprehension. The indexing would be a bit less awkward, in my opinion, if you enumerated starting from 1. I suggest c1 and c2 for characters out of s1 and s2, respectively, but that's a matter of personal taste.

def lcs_len(s1, s2):
    prev_lcs = [0] * (len(s2) + 1)
    curr_lcs = [0] * (len(s2) + 1)
    for c1 in s1:
        curr_lcs, prev_lcs = prev_lcs, curr_lcs
        for j, c2 in enumerate(s2, 1):
            curr_lcs[j] = (
                1 + prev_lcs[j - 1] if c1 == c2 else
                max(prev_lcs[j], curr_lcs[j - 1])
            )
    return curr_lcs[-1]

Answer 2

One way that I can think of, is getting rid of lcs = [[0 for j in xrange(len(s2)+1)] for i in xrange(len(s1)+1)] which uses 2 for() loops.

Let's use just one instead:

string1 = input()
string2 = input()

len_string1 = len(string1)
len_string2 = len(string2)

matrix = [[0] * 5001 for i in range(5001)]
for i in range(0, len_string1):
    for j in range(0, len_string2):
        if string1[i] == string2[j]:
            matrix[i + 1][j + 1] = matrix[i][j] + 1
        else:
            matrix[i + 1][j + 1] = max(matrix[i + 1][j], matrix[i][j + 1])
print(matrix[len_string1][len_string2])

As we just got rid off one for loop, the time complexity for your program would be improved. I also have checked / passed all the test cases from there.

Here is also a nice article about LCS.