python - 没有字符串连接的两个字符串的最长公共(public)序列 O(mn)

Question

我的印象是以下函数的时间复杂度为 O(mn)，其中 m 和 n 是两个字符串的长度。然而，有人不同意，因为他声称字符串连接涉及字符的复制，因此对于长字符串序列，这将不再是 O(mn) 。听起来很有道理。不会连接字符串的 Python 自下而上实现是什么？下面是一个涉及字符串连接的实现。

def lcs_dynamic_programming(s1, s2):
matrix = [["" for x in range(len(s2))] for x in range(len(s1))]
print(matrix)
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

编辑: 例如，考虑 s1 =“thisisatest”，s2 =“testing123testing”，lcs 为“tsitest”

Answer 1

字符串连接的成本O(n)，因为字符串在 Python 中是不可变的，并且每次连接都必须复制到新字符串。为了避免字符串串联，您可以在矩阵构造中使用字符列表代替字符串，并仅在返回时将最终的字符列表连接到字符串中:

def lcs_dynamic_programming(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), ''.join(cs)