python长度最长的公共子序列，无需动态编程

scyqe7ek 于 2021-08-20 发布在 Java

关注(0)|答案(1)|浏览(314)

我正在做一个没有动态规划的查找最长公共子序列（lsc）的练习，到目前为止，我有返回最长公共子序列的代码，但我还需要返回序列的长度，我必须做什么？
这是返回最长公共子序列的代码

def lcs(str1, str2):

    if len(str1) == 0 or len(str2) == 0:
        return ""
    if str1[-1] == str2[-1]:
        return lcs(str1[:-1], str2[:-1]) + str1[-1]

    t1 = lcs(str1[:-1], str2)
    t2 = lcs(str1, str2[:-1])
    if len(t1) > len(t2):
        return t1
    else:
        return t2

如何返回序列的长度？

python lcs

来源：https://stackoverflow.com/questions/68331337/length-longest-common-subsequence-without-dynamic-programming

1条答案

按热度按时间

fnx2tebb1#

只要你的 return 语句返回原始格式中返回的字符串长度：

def lcs(str1, str2):
    if len(str1) == 0 or len(str2) == 0:
        return 0 #len("")
    if str1[-1] == str2[-1]:
        return lcs(str1[:-1], str2[:-1]) + 1
    return max(lcs(str1[:-1], str2),lcs(str1, str2[:-1]))

赞(0）回复(0）举报 2021-08-20

我来回答

python长度最长的公共子序列，无需动态编程

1条答案

相关问题

热门标签

最新问答