下面代码段可以求两个字符串 s1 和 s2 的最长公共子串(LCS),下列相关描述不正确的是( )。

xa736187 单选题 共 个子题
def LCS(str1,str2):
    res = [[0]*len(str2) for _ in range(len(str1))]
    max_len=0
    max_str=[]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i]==str2[j]:
                if i>0 and j>0:
                    res[i][j]=1+res[i-1][j-1]
                else:
                    res[i][j]=1
            if res[i][j]>max_len:
                max_len=res[i][j]
                max_str=[str1[i-max_len+1:i+1]]
            elif res[i][j]==max_len:
                max_str.append(str1[i-max_len:i])
    return max_str
str1,str2=(input().split())
n=LCS(str1,str2)
A

代码的时间复杂度为 O(n^2)

B

代码的空间复杂度为 O(n^2)

C

空间复杂度已经最优

D

采用了动态规划求解

正在加载题目数据…
已答 /
子题
该题型需在试卷/作业中作答,单题练习暂不支持
答案解析
讨论
发布
登录后参与讨论 立即登录
发布讨论需先绑定并验证手机号 去绑定手机号
加载中…
我
我
回复 @
回复 @
发送
还没有人讨论,来发表第一条吧