最长公共序列优化问题

debugcn 发表于 Dev

法伦·皮

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

谢谢。

吴锡ong |

好好尝试。

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

您应该让s1和s2具有s2plus的长度1，即内部循环的长度plus 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

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。