5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice solution @200_success ^^ It beats mine. \$\endgroup\$ – Grajdeanu Alex. May 4 '16 at 8:07
  • \$\begingroup\$ 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! \$\endgroup\$ – Sidharth Samant May 4 '16 at 8:38
  • \$\begingroup\$ Just one question - does using the * operator make the program execution faster than using list comprehension? \$\endgroup\$ – Sidharth Samant May 4 '16 at 8:42
  • 1
    \$\begingroup\$ yes it does :) codereview.stackexchange.com/questions/127458/… \$\endgroup\$ – vegi May 4 '16 at 14:25
2
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.