基础Longest Common Subsequence（LCS）实现报错，如何修正？

错误根源 #

你的代码报错的核心原因是else分支返回了元组，而if分支返回字符串：

• 当s1[n] != s2[m]时，你返回了(lcs(s1[:n], s2), lcs(s1, s2[:m]))，这是一个包含两个字符串的元组；
• 但递归过程中，上层调用会尝试将这个元组和字符串拼接（比如if分支的+ s1[n]），自然触发cannot concatenate tuple with string错误。
• 更重要的是，这个逻辑本身不符合LCS的定义：当最后一个字符不等时，我们需要取两个子问题中更长的那个公共子序列，而非返回两个结果。

基础修正版代码 #

直接修改else分支的逻辑，比较两个子问题的结果长度，返回更长的那个：

def lcs(s1, s2):
    if len(s1) == 0 or len(s2) == 0:
        return ""
    
    n = len(s1) - 1
    m = len(s2) - 1
        
    if s1[n] == s2[m]:
        return lcs(s1[:n], s2[:m]) + s1[n]
    else:
        # 计算两个子问题的结果
        sub1 = lcs(s1[:n], s2)
        sub2 = lcs(s1, s2[:m])
        # 返回长度更长的序列，长度相同时返回任意一个即可（LCS可能不唯一）
        return sub1 if len(sub1) > len(sub2) else sub2

s1 = "abcbac"
s2 = "babacc"
res = lcs(s1, s2)
print(res)  # 输出示例：babac 或 abacc（均为正确的LCS）

优化版（避免重复计算） #

上面的递归版本会大量重复计算相同的子问题（比如lcs("abc", "bab")可能被多次调用），可以用记忆化缓存提升效率。这里改用索引传递的方式，配合lru_cache装饰器：

from functools import lru_cache

@lru_cache(maxsize=None)
def lcs(s1, s2, i, j):
    # i和j分别表示s1前i个字符、s2前j个字符的子问题
    if i == 0 or j == 0:
        return ""
    if s1[i-1] == s2[j-1]:
        return lcs(s1, s2, i-1, j-1) + s1[i-1]
    else:
        sub1 = lcs(s1, s2, i-1, j)
        sub2 = lcs(s1, s2, i, j-1)
        return sub1 if len(sub1) > len(sub2) else sub2

s1 = "abcbac"
s2 = "babacc"
res = lcs(s1, s2, len(s1), len(s2))
print(res)

内容的提问来源于stack exchange，提问作者v1998199904