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.