最长公共序列优化问题

Question

我正在尝试解决在两个字符串之间找到最长公共序列的问题。我使用动态规划 (DP) 并尝试对其进行优化。但是我仍然在 HackerRank 上超时，我不知道为什么。我使用迭代版的Hunt-Szymanski算法。

我没有使用一个矩阵，而是只使用了两行并将它们互换。我还删除了字符串开头和结尾的所有常见字符。我还使用了算法的迭代版本。我还能如何优化它？

这是我的代码：

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

谢谢。

Answer 1

很好的尝试。

请注意，您使用索引 i 在外循环中循环遍历 s1，在内部循环中使用索引 j 循环遍历 s2。

你应该让s1和s2的长度为s2加上1，内环长度加上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

最长公共序列优化问题

Longest Common Sequence optimization problem

python

algorithm

optimization

dynamic-programming

longest-substring