如何修改递归LCS长度计算函数使其返回最长公共子序列本身

核心改造思路 #

你原有函数仅返回LCS长度，只需要把递归返回值从长度数值替换为拼接好的LCS字符串，即可实现需求，逻辑和原长度计算逻辑完全对齐：

• 边界条件：当任一索引超出对应序列长度时，返回空字符串（对应原逻辑的长度0）
• 当前字符匹配：将当前字符拼接到后续递归得到的LCS字符串前返回
• 当前字符不匹配：分别递归移动两个索引的分支，返回两个分支中长度更长的字符串即可

实现代码 #

基础朴素版本（和原逻辑完全对应） #

def lcs_recursive_str(seq1, seq2, idx1 = 0, idx2 = 0):
    # 边界：超出序列长度返回空串
    if idx1 == len(seq1) or idx2 == len(seq2):
        return "" 
    # 字符匹配，将当前字符加入结果
    if seq1[idx1] == seq2[idx2]:
        return seq1[idx1] + lcs_recursive_str(seq1, seq2, idx1 + 1, idx2 + 1)
    # 字符不匹配，取更长的子问题结果
    else:
        option1 = lcs_recursive_str(seq1, seq2, idx1 + 1, idx2)
        option2 = lcs_recursive_str(seq1, seq2, idx1, idx2 + 1)
        return option1 if len(option1) > len(option2) else option2

测试调用 #

seq1 = 'serendipitous'
seq2 = 'precipitation'
print(lcs_recursive_str(seq1, seq2))
# 输出结果：reipito

优化版本（记忆化缓存，解决重复子问题性能问题） #

朴素递归存在大量重复计算的子问题，序列长度超过20后性能会大幅下降，添加记忆化缓存即可优化：

from functools import lru_cache

# 装饰器开启缓存，避免重复计算
@lru_cache(maxsize=None)
def lcs_recursive_str(seq1, seq2, idx1 = 0, idx2 = 0):
    if idx1 == len(seq1) or idx2 == len(seq2):
        return "" 
    if seq1[idx1] == seq2[idx2]:
        return seq1[idx1] + lcs_recursive_str(seq1, seq2, idx1 + 1, idx2 + 1)
    else:
        option1 = lcs_recursive_str(seq1, seq2, idx1 + 1, idx2)
        option2 = lcs_recursive_str(seq1, seq2, idx1, idx2 + 1)
        return option1 if len(option1) > len(option2) else option2

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