Задача оптимизации самой длинной общей последовательности - PullRequest
Новая
       29

Задача оптимизации самой длинной общей последовательности

1 голос
/ 17 апреля 2020

Я пытаюсь решить проблему, которая находит длинную общую последовательность между двумя строками. Я использовал динамическое программирование c (DP) и попытался его оптимизировать. Но я все еще получаю тайм-аут на HackerRank, и я не знаю почему. Я использую итерационную версию алгоритма Ханта – Шиманского.

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

Это мой код: 

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

Спасибо.

1 Ответ

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

Хорошая попытка.

Обратите внимание, что вы используете индекс от i до l oop до s1 во внешнем l oop и от j до l oop до s2 во внутренней l oop.

Вы должны позволить s1 и s2 иметь длину s2 плюс 1, внутреннюю l oop длину плюс 1.

Кроме того, вы по ошибке используете j для доступа к s1 и i для доступа к s2 в своей реализации.

Наконец, чтобы преодолеть проблему тайм-аута, вместо обычного Python, используйте вместо этого PyPy. 

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)
    row1 = [0]*(len(s2)+1)
    row2 = [0]*(len(s2)+1)
    for i in range(1,len(s1)+1):
        for j in range(1,len(s2)+1):
            #if s1[j-1]==s2[i-1]:
            if s1[i-1] == s2[j-1]:
                row2[j]=row1[j-1]+1
            else:
                row2[j]=max(row2[j-1], row1[j])
        row1=row2
        #row2=[0]*(len(s1)+1)
        row2 = [0]*(len(s2)+1)
    return row1[-1]+nr
...