递归打印所有最长公共子序列(LCS)代码结果异常问题排查

你的代码出现异常的核心原因有两个：

• dp数组索引不匹配
  你构造的dp数组是(m+1)*(n+1)维度，dp[i][j]代表text1前i个字符、text2前j个字符的LCS长度。但你在递归函数里直接用text1的0起始下标m取dp[m-1][n]，索引完全对应不上，导致递归路径判断错误，生成了大量长度不符合要求的短序列。
• 递归分支的引用冲突
  当dp[m-1][n] == dp[m][n-1]需要同时走向上、向左两个方向递归时，你给两个分支传了同一个output列表对象，两个分支的修改会互相干扰；加上你取消注释output.remove(elem)时，遍历的是列表副本，删除原列表元素时如果存在重复元素只会删除第一个匹配项，直接导致大量路径丢失，最后只会返回1个结果。

class Solution:
    def LcsHelper(self, text1, text2, dp, output, m, n):
        # 递归终止条件：任意字符串遍历完成
        if m < 0 or n < 0:
            return output
        # 字符相等，拼接当前字符到所有结果前
        if text1[m] == text2[n]:
            out = []
            for elem in output:
                out.append(text1[m] + elem)
            return self.LcsHelper(text1, text2, dp, out, m-1, n-1)
        # 字符不等，判断递归方向，注意dp索引要和当前字符位置对应
        # dp[m+1][n+1] 对应当前text1[m]、text2[n]的位置的LCS长度
        if dp[m][n+1] > dp[m+1][n]:
            # 向上走，text1左移一位
            return self.LcsHelper(text1, text2, dp, output, m-1, n)
        elif dp[m][n+1] < dp[m+1][n]:
            # 向左走，text2左移一位
            return self.LcsHelper(text1, text2, dp, output, m, n-1)
        else:
            # 两个方向都可以，分别递归后合并结果，注意要传output的副本避免互相干扰
            out1 = self.LcsHelper(text1, text2, dp, output.copy(), m-1, n)
            out2 = self.LcsHelper(text1, text2, dp, output.copy(), m, n-1)
            return out1 + out2

    def printlongestCommonSubsequence(self, text1, text2):
        m, n = len(text1), len(text2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        # 构造dp矩阵
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])
        # 递归获取所有LCS，最后去重
        all_lcs = self.LcsHelper(text1, text2, dp, [""], m-1, n-1)
        return list(set(all_lcs))

s = Solution()
text1 = "BDCABA"
text2 = "ABCBDAB"
print(s.printlongestCommonSubsequence(text1, text2))
# 输出（顺序可能不同）：['BDAB', 'BCAB', 'BCBA']

所有结果长度均为4，和LCS长度一致，无无效短序列。

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