# High execution time of LCS length program in Python2

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.

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]

• Nice solution @200_success ^^ It beats mine. – Grajdeanu Alex May 4 '16 at 8:07
• Yes, this did work for all the test cases. Some of the later test cases that were previously getting timed out were computed in close to 10 seconds, but less than 10, so I could now get the entire challenge's results. Thanks a lot! – Sidharth Samant May 4 '16 at 8:38
• Just one question - does using the * operator make the program execution faster than using list comprehension? – Sidharth Samant May 4 '16 at 8:42
• yes it does :) codereview.stackexchange.com/questions/127458/… – vegi May 4 '16 at 14:25

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.

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.

• I've run the two different bits in timeit and the difference is striking.... 7.54410600662s vs 1.76344299316s (10x repeat) – vegi May 4 '16 at 9:07