时间戳

首页 > 解决方案 > 最长公共序列优化问题

python - 最长公共序列优化问题

问题描述

我正在尝试解决在两个字符串之间找到最长公共序列的问题。我使用了动态编程（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

谢谢你。

标签： pythonalgorithmoptimizationdynamic-programminglongest-substring

解决方案

很好的尝试。

请注意，您使用 index在外循环i中循环，并在内部循环中使用 index 循环。s1js2

你应该让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

推荐阅读