Python求两个字符串最长公共子序列代码实例

一、问题描述 给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。比如字符串1：BDCABA；字符串2：ABCBDAB。则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA 二、算法求解 这是一个动态规划的题目。对于可用动态规划求解的问题，一般有两个特征：①最优子结构；②重叠子问题 ①最优子结构 设X=(x1,x2,…,xn)和Y=(y1,y2,…,ym)是两个序列，将X和Y的最长公共子序列记为LCS(X,Y) 找出LCS(X,Y)就是一个最优化问题。因为，我们需要找到X和Y中最长的那个公共子序列。而要找X和Y的LCS，首先考虑X的 【Python求两个字符串最长公共子序列】 在编程领域，字符串操作是常见任务之一，而寻找两个字符串的最长公共子序列（LCS）是其中的一个经典问题。LCS是指两个字符串中都出现过的最长的连续子序列，但不考虑字符在原始字符串中的相对位置。例如，字符串"ABCDGH"和"ACDFGHR"的LCS是"ADH"，长度为3。 **一、问题描述** 给定两个字符串，目标是找到这两个字符串的最长公共子序列。例如，字符串1 "BDCABA" 和字符串2 "ABCBDAB"，它们的LCS长度为4，LCS为 "BCBA"。解决这个问题需要使用动态规划的方法。 **二、动态规划算法** 动态规划是一种有效处理具有最优子结构和重叠子问题的优化问题的方法。在LCS问题中： 1. **最优子结构**：LCS(X,Y) 的最优解可以由其子问题的最优解得出。如果X的最后一个字符xn等于Y的最后一个字符ym，LCS(X,Y)等于LCS(Xn-1,Ym-1)加1；否则，LCS(X,Y)将是LCS(Xn-1,Ym)和LCS(Xn,Ym-1)中较长的一个。 2. **重叠子问题**：在递归求解LCS时，会遇到许多相同或相似的子问题。例如，LCS(Xn-1,Ym)和LCS(Xn,Ym-1)都会涉及到LCS(Xn-1,Ym-1)，这是重叠子问题的表现。为了避免重复计算，动态规划使用一个二维数组来存储中间结果，从而减少计算量。 **三、动态规划解法** LCS问题的动态规划解法通常使用一个二维数组C[i][j]，其中C[i][j]表示字符串1的前i个字符和字符串2的前j个字符的最长公共子序列的长度。状态转移方程可以表示为： - 如果str1[i-1] == str2[j-1]，则C[i][j] = C[i-1][j-1] + 1； - 否则，C[i][j] = max(C[i-1][j], C[i][j-1])。 Python实现如下： ```python def longestCommonSequences(str1, str2): m, n = len(str1), len(str2) C = [[0] * (n+1) for _ in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): if str1[i-1] == str2[j-1]: C[i][j] = C[i-1][j-1] + 1 else: C[i][j] = max(C[i-1][j], C[i][j-1]) return C[m][n] ``` 这个函数返回的就是两个字符串的最长公共子序列的长度。要获取具体的LCS字符串，可以从C[m][n]回溯到C[1][1]，记录下每次转移过程中匹配的字符，形成最终的LCS。 总结来说，Python求解两个字符串的最长公共子序列利用动态规划避免了重复计算，实现了从指数级时间复杂度到线性时间复杂度的转换，提高了效率。通过构建二维数组C，我们可以高效地找到字符串间的最长公共子序列，这对于处理大量字符串数据的场景非常有用。