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

下面我会给您详细讲解如何使用Python解决求两个字符串最长公共子序列的问题。

什么是最长公共子序列？

最长公共子序列，简称LCS（Longest Common Subsequence），是两个或多个序列（如字符串或数组）中它们的子序列，在所有可能的子序列中最长的一个。

举个简单的例子，如果有两个字符串 S1 = "ABCBDAB" 和 S2 = "BDCABA"，它们的最长公共子序列为 "BCBA"。

求解最长公共子序列的基本思路

那么，我们该如何使用 Python 求解两个字符串的最长公共子序列呢？其实，我们可以使用动态规划（Dynamic Programming）算法求解。

动态规划算法的基本思路是把原问题分解为相对简单的子问题的方式来求解问题的过程。在动态规划算法中，我们通常使用一个表格来存储每个子问题的最优解，从而避免重复计算，提高效率。

在求解两个字符串的最长公共子序列时，我们可以用一个二维表格来记录每个子问题的最优解。表格的行表示字符串 S1 的字符，表格的列表示字符串 S2 的字符。对于任意一个位置 (i, j)，如果 S1[i] 等于 S2[j]，那么在这个位置的最长公共子序列长度等于它左上角的值加 1；否则，在这个位置的最长公共子序列长度等于它左方和上方的值的最大值。

根据上述思路，我们可以得到以下 Python 代码：

def lcs(str1, str2):
    m, n = len(str1), len(str2)
    # 初始化一个二维的动态规划表格
    dp = [[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]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # 返回最长公共子序列长度
    return dp[m][n]

在这段代码中，我们首先初始化了一个 m+1 行、n+1 列的二维的动态规划表格 dp，其中 dp[i][j] 表示以字符串 str1 的第 i 个字符结尾和以字符串 str2 的第 j 个字符结尾的最长公共子序列长度。然后，我们利用两层循环计算出每个子问题的最优解，最后返回 dp[m][n]，也就是所求的最长公共子序列的长度。

接下来，我们用两个字符串 S1 = "ABCBDAB" 和 S2 = "BDCABA" 来演示一下这个算法的具体执行流程。根据上述代码，求解的过程可以表示为一个二维表格，如下图所示：

char\S  B  D  C  A  B  A
    +------------------
  | |0|0|0|0|0|0|0|
A |0|0|0|0|1|1|1|1|
B |0|1|1|1|1|2|2|2|
C |0|1|1|2|2|2|2|2|
B |0|1|1|2|2|3|3|3|
D |0|1|2|2|2|3|3|3|
A |0|1|2|2|3|3|4|4|
B |0|1|2|2|3|4|4|5|

其中，第一行和第一列表示字符串 S1 和 S2 为空字符串的情况。

根据这个表格，我们可以看出，字符串 S1 和 S2 的最长公共子序列为 "BCBA"，长度为 4。

总结

通过以上的例子，我们可以看到，利用动态规划算法，通过一个二维的表格记录每个子问题的最优解，可以很快、很简单地求解两个字符串的最长公共子序列。

同时，这种求解方法也可以应用到其他问题中，只要能够把原问题分解成子问题，并使用一个表格记录每个子问题的最优解。