In [3]:

    

import numpy as np


    

In [29]:

    

def lcs(x: str, y: str) -> int:
    n = len(x)
    m = len(y)
    
    # initialize table to zeros
    l = np.zeros((n + 1, m + 1))
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                l[i, j] = 1 + l[i - 1, j - 1]
            else:
                l[i, j] = l[i, j - 1]
    
    # return the max of the last column
    return l[:, m].max()


    

In [30]:

    

lcs('abdbabfgd', 'betfdbfafr')


    

    
Out[30]:





4.0