Python 中的最长公共子序列

我试图找到两个字符串之间的最长公共子序列。

我看了这个教程https://www.youtube.com/watch?v=NnD96abizww https://www.youtube.com/watch?v=NnD96abizww

并写道：

# Longest Common Subsequence

def lcs(s1, s2):
    matrix = [ [0 for x in range(len(s2))] for x in range(len(s1)) ]
    cs = ""
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i]==s2[j]:
                if i==0 or j==0:
                    matrix[i][j] = 1
                    cs += s1[i]
                else:
                    matrix[i][j] = matrix[i-1][j-1] + 1
                    cs += s1[i]
            else:
                if i==0 or j==0:
                    matrix[i][j] = 0
                else:
                    matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])

    return matrix[len(s1)-1][len(s2)-1], cs


print(lcs("abcdaf", "acbcf"))  



I get (3, 'abccaf')

这显然是错误的，应该是 4 abcf。

不知道哪一步出了问题。一个普遍的问题是程序员通常需要多长时间才能“得到”这类问题？

您的代码有两个主要问题导致算法输出错误的答案。

if i == 0 or j == 0在第 16 行

只要跟随视频就可以看出，当s1[1] != s2[j]，因为“ab”和“a”的最长公共子序列的长度为 1，尽管您的算法设置matrix[0][1] = 0对于这个例子。所以你需要删除这个if语句。当你这样做时，你必须考虑什么max(matrix[i-1][j], matrix[i][j-1])为i == 0 or j == 0。现在有两种不同的方法：

1. 明确的一个：

   max(matrix[i-1][j] if i != 0 else 0, 
       matrix[i][j-1] if j != 0 else 0)
   

2. 隐式的：

   max(matrix[i-1][j], matrix[i][j-1])
   

   这个是有效的，因为在 Python 中负索引用于获取列表的最后一项，在本例中这些项为 0。

cs += s1[i]在第 11/14 行

例如，如果您发现“a”和“abcd”的最长公共子序列是“a”，则您的算法将“a”和“abcda”的最长公共子序列设置为“aa”，这是没有意义的。我很难解释why它不是这样工作的，所以我建议你看几个例子，也许使用http://pythontutor.com/visualize.html http://pythontutor.com/visualize.html

Solution

要解决这两个问题，您可以使用矩阵来存储为较小问题找到的最长公共子序列。你最终会得到这样的结果：

def lcs(s1, s2):
    matrix = [["" for x in range(len(s2))] for x in range(len(s1))]
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                if i == 0 or j == 0:
                    matrix[i][j] = s1[i]
                else:
                    matrix[i][j] = matrix[i-1][j-1] + s1[i]
            else:
                matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1], key=len)

    cs = matrix[-1][-1]

    return len(cs), cs

print(lcs("abcdaf", "acbcf"))  

该特定实现仅返回一种可能的结果。您可以尝试实现一个给出所有最长公共序列的算法作为练习。也许看看维基百科页面 https://en.wikipedia.org/wiki/Longest_common_subsequence_problem正如 גלעד ברקן 建议的

需要多长时间才能“了解”您的代码不起作用的原因？

显然没有明确的答案。思考示例总是有帮助的，就算法而言，维基百科通常有一个很好的伪代码，您可以基于它来实现。我想说，当你熟悉算法中涉及的概念和数据结构时，你应该能够在一天之内实现它（但我绝对不是专家）。一般来说，搜索代码中的逻辑错误可能需要几天时间，具体取决于代码的大小。我强烈推荐练习这种结构化、算法和数学思维投影网 http://projecteuler.net.