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.

## No comments:

## Post a Comment