Как ускорить алгоритм LCS в python? - PullRequest
Новая
       20

Как ускорить алгоритм LCS в python?

0 голосов
/ 14 марта 2020

Я выполнил упражнение под названием «общий ребенок» (найти самую длинную общую подпоследовательность из двух строк ввода) на хакерранке, проблема в том, что мой алгоритм не был достаточно быстрым для завершения. Во-первых, я думал, что это было сверхурочно моим процессом создания массива, я пытался ускорить, но это было не лучше. Есть ли способ улучшить мой алгоритм? (Это упражнение не позволяет импортировать numpy). В любом случае, большое вам спасибо.

Вот мой код 

def commonChild(s1, s2):
    l = len(s1)+1
    lst = []
    for i in range(l):
        lst.append([0]*l)
        for j in range (l):
            if(i == 0 or j == 0):
                lst[i][j] = 0
            elif(s1[i-1]==s2[j-1]):
                lst[i][j] = lst[i-1][j-1]+1
            else:
                lst[i][j] = max(lst[i-1][j],lst[i][j-1])
    return int(lst[-1][-1])
...