Hackerrank Common Child - проблема тайм-аута - PullRequest
Новая
       17

Hackerrank Common Child - проблема тайм-аута

0 голосов
/ 16 апреля 2020

Я пытаюсь решить проблему, которая находит длинную общую последовательность между двумя строками. Я использовал DP и попытался оптимизировать его, однако у меня все еще есть тайм-аут, и я не знаю почему. Вместо того чтобы использовать одну матрицу, я использовал только две строки и чередовал их, я также исключил все общие символы в начале и конце строк. Как еще я могу оптимизировать это? Спасибо. Это мой код: 

def commonChild(s1, s2):
    nr = 0
    while s1[0]==s2[0]:
        nr+=1
        s1=s1[1::]
        s2=s2[1::]
    while s1[-1]==s2[-1]:
        nr+=1
        s1=s1[0:-1]
        s2=s2[0:-1]

    row1 = [0]*(len(s1)+1)
    row2 = [0]*(len(s1)+1)


    for i in range(1,len(s1)+1):
        for j in range(1,len(s2)+1):


            if s1[j-1]==s2[i-1]:
                row2[j]=row1[j-1]+1


            else:

                row2[j]=max(row2[j-1], row1[j])


        row1=row2
        row2=[0]*(len(s1)+1)


    return row1[-1]+nr
...