No solution works for Longest Common Subsequence problem

Question

I was going through common child problem on hackerrank. It is nothing but a Longest Common Subsequence problem.

Tried it solving as follows:

def commonChild(s1, s2):
    LCS_table = [[0 for _ in range(len(s2)+1)] 
                 for _ in range(len(s1)+1)
                ]              
    for i in range(1,len(s1)+1):
        for j in range(1,len(s2)+1):            
            if s1[i-1] == s2[j-1]: #Mistake not [i] & [j] but [i-1] & [j-1] Ref: $A1
                LCS_table[i][j] = LCS_table[i-1][j-1] + 1
            else:
                LCS_table[i][j] = max(LCS_table[i-1][j], LCS_table[i][j-1])
    return LCS_table[-1][-1]

Eight test cases passed, but six test cases gave "Time Limit Exceeded" error. I quickly googled online solutions and tried them. But for all of them was able to pass more than half of the test cases, but failing at other with time limit exceeded error:

Sol 2 ref

def commonChild(a, b):
    m = len(a)
    n = len(b)
    prev = [0 for x in range(n + 1)]
    for i in range(1, m + 1):
        curr = [0 for x in range(n + 1)]
        for j in range(1, n + 1):
            curr[j] = max(prev[j], curr[j - 1])
            if a[i - 1] == b[j - 1]:
                curr[j] = max(curr[j], prev[j - 1] + 1)
        prev = curr
    return curr[n]

Sol 3 ref

def commonChild(s1, s2):
    m = [[0]*(len(s2)+1) for _ in range(len(s1)+1)]
    for i,c in enumerate(s1,1):
        for j,d in enumerate(s2,1):
            if c == d:
                m[i][j] = m[i-1][j-1]+1
            else:
                m[i][j] = max(m[i][j-1],m[i-1][j])
                   
    return m[-1][-1]

Are we all missing some idea to make it execute even faster?

Answer 1

@Rnj - if you switch to PyPy3 - all three versions will pass with flying color. So your logic is all sound, but the CPython just too slow in this particular case unfortunately.

I've tried many times earlier with diff. approaches - until @Kelly reminded me the faster version is also available there. Lesson learned.

Big kudos to @Kelly.

Answer 2

Here's a version that gets accepted with Python 3, i.e., doesn't need PyPy:

def commonChild(s1, s2):
    L = [0] * len(s2)
    for c in s1:
        p = 0
        L = [
            p := (q+1 if c==d else r if p < r else p)
            for d, q, r in zip(s2, [0]+L, L)
        ]
    return L[-1]

It's about five times faster than your solutions in my own testing.

Main tricks are to avoid max(), avoid reading by index (zipping instead) and avoid writing by index (use list comp instead).

My L is the latest row of the LCS_table, and my variables p, q and r mean LCS_table[i][j-1], LCS_table[i-1][j-1] and LCS_table[i-1][j].

Thanks to @Daniel for testing this at HackerRank (I can't, their editor is utterly unusable for me on my phone).

---

For some more clarity, it's:

(where "p+1" means "next p-value", the one computed in the ... of p := (...) and then assigned to p)

To help you visualize what how above zipping works:

>>> L = [1,2,3,4,5,6]
>>> s2 = ['a','b','c','d','e','f']
>>> zip(s2,[0]+L,L)
[('a', 0, 1), ('b', 1, 2), ('c', 2, 3), ('d', 3, 4), ('e', 4, 5), ('f', 5, 6)]

Also whats := in list comprehension?