Dynamic Programming Solution to finding if one string is a 'shuffle' of two others

is_shuffle.py

'''Let x, y, and z, be strings over some alphabet Σ, where |z| = |x| + |y| (here |w|
denotes the length of a string w). We say that z is a shuffle of x and y if there are (possibly empty)
strings x1, x2, . . . , xk and y1, y2, . . . , yk so that x = x1x2 . . . xk, y = y1y2 . . . yk, and z = x1y1x2y2 . . . xkyk.
Intuitively, z can be constructed as the concatenation of pieces of x and y, in the order in which these
pieces appear in x and y, respectively. For example, 'alabama' is a shuffle of 'aba' and 'lama', but 'amalaba' is not.

We want an algorithm that, given as input three strings x, y, and z such that |z| = |x| + |y|, returns
true if z is a shuffle of x and y, and returns false otherwise.

Answer: Dynamic Programming
'''

def is_shuffle(x,y,z):
    '''Returns True iff z is a 'shuffled' string of x and y (i.e. some
    concatenations of pieces of x and y can be combined in order to form z)'''
    
    assert len(x) + len(y) == len(z)
    
    S = [[k for k in range(len(y)+1)] for m in range(len(x)+1)]
    
    print S
    
    for i in range(len(x)+1):
        if x[:i] == z[:i]:
            S[i][0] = True
        else:
            S[i][0] = False
    
    for j in range(len(y)+1):
        if y[:j] == z[:j]:
            S[0][j] = True
        else:
            S[0][j] = False
    
    print S
    
    for i in range(1, len(x)+1):
        for j in range(1, len(y)+1):
            print i,j, S[i-1][j], z[:i+j-1], x[i-1], S[i][j-1], z[:i+j-1], y[j-1], z[:i+j]
            
            if S[i-1][j] is True and z[:i+j-1] + x[i-1] == z[:i+j]:
                S[i][j] = True
            
            elif S[i][j-1] is True and z[:i+j-1] + y[j-1] == z[:i+j]:
                S[i][j] = True
            
            else:
                S[i][j] = False

    
    return S[len(x)][len(y)]

assert is_shuffle('aba', 'lama', 'alabama')
assert is_shuffle('va', 'arible', 'variable')
assert not is_shuffle('aba', 'lama', 'amalaba')
assert is_shuffle('ca', 'nada', 'canada')