没有字符串连接的两个字符串的最长公共序列 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 中是不可变的并且必须为每个连接复制到一个新字符串。为避免字符串连接，您可以在矩阵构造中使用字符列表代替字符串，并且仅在 return:

时将最终字符列表连接到字符串中

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)

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

Longest Common Sequence O(mn) of two strings without string concatenation

python

big-o

time-complexity

lcs