Longest Common Sequence optimization problem

Question

I am trying to solve a problem which finds Longest Common Sequence between two strings. I used dynamic programming (DP) and I tried to optimize it. But I still get a timeout on HackerRank and I do not know why. I use the iterative version of Hunt–Szymanski algorithm.

Instead of using one matrix, I used only two rows and I interchange them. I also eliminated all common characters at the beginning and the end of the strings. I also used the iterative version of the algorithm. How else could I optimize this?

This is my code:

def commonChild(s1, s2):
    nr = 0
    while s1[0]==s2[0]:
        nr+=1
        s1=s1[1::]
        s2=s2[1::]
    while s1[-1]==s2[-1]:
        nr+=1
        s1=s1[0:-1]
        s2=s2[0:-1]

    row1 = [0]*(len(s1)+1)
    row2 = [0]*(len(s1)+1)


    for i in range(1,len(s1)+1):
        for j in range(1,len(s2)+1):


            if s1[j-1]==s2[i-1]:
                row2[j]=row1[j-1]+1


            else:

                row2[j]=max(row2[j-1], row1[j])


        row1=row2
        row2=[0]*(len(s1)+1)


    return row1[-1]+nr     

Thank you.

Answer 1

Good attempt.

Notice that you use index i to loop through s1 in the outer loop and index j to loop through s2 in the inner loop.

You should let s1 and s2 to have the length of s2 plus 1, the inner loop length plus 1.

Also, you mistakenly use j to access s1 and i to access s2 in your implementation.

Lastly, to overcome the timeout issue, rather than the regular Python, use PyPy instead.

def commonChild(s1, s2):
    nr = 0
    while s1[0]==s2[0]:
        nr+=1
        s1=s1[1::]
        s2=s2[1::]
    while s1[-1]==s2[-1]:
        nr+=1
        s1=s1[0:-1]
        s2=s2[0:-1]
    #row1 = [0]*(len(s1)+1)
    #row2 = [0]*(len(s1)+1)
    row1 = [0]*(len(s2)+1)
    row2 = [0]*(len(s2)+1)
    for i in range(1,len(s1)+1):
        for j in range(1,len(s2)+1):
            #if s1[j-1]==s2[i-1]:
            if s1[i-1] == s2[j-1]:
                row2[j]=row1[j-1]+1
            else:
                row2[j]=max(row2[j-1], row1[j])
        row1=row2
        #row2=[0]*(len(s1)+1)
        row2 = [0]*(len(s2)+1)
    return row1[-1]+nr