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]

StackExchange Code Review Q#127448, answer score: 4