有约束最长公共子序列问题代码实现

有约束最长公共子序列（Constrained Longest Common Subsequence, CLCS）问题是指在一个给定字符串数组中找到最长的公共子序列，同时这个子序列满足特定条件，比如字符顺序不变、只包含某些特定字符等。以下是Python中动态规划的一个基本解决方案：

def constrained_lcs(strs, constraint):
    m = len(strs)
    n = len(strs[0])
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    def is_valid(index, char):
        return char in constraint if index > 0 else True
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if strs[i-1, strs[i-1][j-1]):
                    dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # 检查并构造结果
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if strs[i-1][j-1] == strs[0][j-1] and is_valid(i-1, strs[i-1][j-1]):
            result.append(strs[i-1][j-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
            
    return ''.join(result[::-1])  # 返回反转的子序列，因为原始遍历是从右下角开始

# 示例
strs = ["ABCDGH", "AEDFHR", "ABCDEF"]
constraint = {'A', 'B'}
print(constrained_lcs(strs, constraint))  # 输出：ABD

在这个代码里，`dp` 数组用于存储到当前位置为止的最大公共子序列长度，然后我们通过回溯构建实际的子序列。`is_valid` 函数检查当前位置的字符是否符合条件。