Longest Common Subsequence of three strings
<p>I've written these functions (which work) to find the longest common subsequence of two strings.</p>

<pre><code>def lcs_grid(xs, ys):
    grid = defaultdict(lambda: defaultdict(lambda: (0,"")))
    for i,x in enumerate(xs):
        for j,y in enumerate(ys):
            if x == y:
                grid[i][j] = (grid[i-1][j-1][0]+1,'\\')
            else:
                if grid[i-1][j][0] &gt; grid[i][j-1][0]:
                    grid[i][j] = (grid[i-1][j][0],'&lt;')
                else:
                    grid[i][j] = (grid[i][j-1][0],'^')

    return grid

def lcs(xs,ys):
    grid = lcs_grid(xs,ys)
    i, j = len(xs) - 1, len(ys) - 1

    best = []
    length,move = grid[i][j]
    while length:
        if move == '\\':
            best.append(xs[i])
            i -= 1
            j -= 1
        elif move == '^':
            j -= 1
        elif move == '&lt;':
            i -= 1
        length,move = grid[i][j]

    best.reverse()
    return best
</code></pre>

<p>Has anybody a proposition to modify the functions s.t. they can print the longest common subsequence of three strings? I.e. the function call would be: <code>lcs(str1, str2, str3)</code></p>

<p>Till now, I managed it with the 'reduce'-statement, but I'd like to have a function that really prints out the subsequence without the 'reduce'-statement.</p>
