Longest Common Subsequence of Three Sequences

And finally, the last one of this group of Dynamic Programming problems. Actually, from the algorithmic point of view this is the less interesting one, being just a variation on the previous one. Now we have in input three sequences instead of two, still we have to get the longest subsequence among them.

The interest here is all in extending the algorithm to work with a three-dimensional cache. Basically just an implementation issue, that each programming language could solve in its own way.

Here is how I did it in python:

def solution_dp(a, b, c):
    cube = []
    for m in range(len(c) + 1):  # 1
        sheet = [[0] * (len(b) + 1)]
        for n in range(1, len(a) + 1):
            sheet.append([0] * (len(b) + 1))
        cube.append(sheet)

    for i in range(1, len(cube)):
        for j in range(1, len(cube[0])):
            for k in range(1, len(cube[0][0])):
                if a[j - 1] == b[k - 1] == c[i - 1]:  # 2
                    cube[i][j][k] = cube[i - 1][j - 1][k - 1] + 1
                else:
                    cube[i][j][k] = max(cube[i - 1][j][k], cube[i][j - 1][k], cube[i][j][k - 1])

    return cube[-1][-1][-1]

1. If you compare this code with the one for the 2-sequences problem, you would see how the difference is all in this extra for-loop. Now the cache is a three dimensional matrix (actually, it is not a cube but a parallelepiped, you could guess why I used a wrong name here).
2. The comparisons get now three way. Luckily, python helps us keeping them readable.

Once you manage correctly the three-level loop, the job is done.

I have pushed the complete python script and its test case to GitHub.