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的最后⼀个元素和Y的最后⼀个元素。
⑴如果xn=ym，即X的最后⼀个元素与Y的最后⼀个元素相同，这说明该元素⼀定位于公共⼦序列中。因此，现在只需要：LCS(Xn-1,Ym-1)
LCS(Xn-1,Ym-1)就是原问题的⼀个⼦问题。为什么叫⼦问题？因为它的规模⽐原问题⼩。
为什么是最优的⼦问题？因为我们要的是Xn-1和Ym-1的最长公共⼦序列啊。最长的！换句话说就是最优的那个。
⑵如果xn!=ym，这下要⿇烦⼀点，因为它产⽣了两个⼦问题：LCS(Xn-1,Ym)和LCS(Xn,Ym-1)
因为序列X和序列Y的最后⼀个元素不相等，那说明最后⼀个元素不可能是最长公共⼦序列中的元素。
LCS(Xn-1,Ym)表⽰：最长公共序列可以在(x1,x2,...xn-1)和(y1,y2,...,ym)中。
LCS(Xn,Ym-1)表⽰：最长公共序列可以在(x1,x2,...xn)和(y1,y2,...,ym-1)中。
求解上⾯两个⼦问题，得到的公共⼦序列谁最长，那谁就是LCS(X,Y)。⽤数学表⽰就是：
LCS=max{LCS(Xn-1,Ym),LCS(Xn,Ym-1)}
由于条件⑴和⑵考虑到了所有可能的情况。因此，我们成功的把原问题转化成了三个规模更⼩的问题。
②重叠⼦问题
重叠⼦问题是什么？就是说原问题转化成⼦问题后，⼦问题中有相同的问题。子字符串是什么
原问题是：LCS(X,Y)。⼦问题有❶LCS(Xn-1,Ym-1)❷ LCS(Xn-1,Ym)❸ LCS(Xn,Ym-1)
乍⼀看，这三个问题是不重叠的。可本质上它们是重叠的，因为它们只重叠了⼀⼤部分。举例：
第⼆个⼦问题：LCS(Xn-1,Ym)就包含了问题❶LCS(Xn-1,Ym-1)，为什么？
因为，当Xn-1和Ym的最后⼀个元素不相同时，我们⼜需要将LCS(Xn-1,Ym-1)进⾏分解：分解成：LCS(Xn-1,Ym-1)和
LCS(Xn-2,Ym)
也就是说：在⼦问题的继续分解中，有些问题是重叠的。
由于像LCS这样的问题，它具有重叠⼦问题的性质，因此：⽤递归来求解就太不划算了。国为采⽤递归，它重复地求解了⼦问题，⽽且需要注意的是，所有⼦问题加起来的个数是指数级的。
那么问题来了，如果⽤递归求解，有指数级个⼦问题，故时间复杂度是指数级的。这指数级个⼦问题，
难道⽤了动态规划，就变成多项式时间了？？
关键是采⽤动态规划时，并不需要去⼀⼀计算那些重叠了的⼦问题。或者说：⽤了动态规划之后，有些⼦问题是通过“查表”直接得到的，⽽不是重新⼜计算⼀遍得到的。举个例⼦：⽐如求Fib数列。
求fib(5)，分解成了两个⼦问题：fib(4)和fib(3)，求解fib(4)和fib(3)时，⼜分解了⼀系列的⼩问题...
从图中可以看出：根的左右⼦树：fib(4)和fib(3)下，是有很多重叠的！⽐如，对于fib(2)，它就⼀共出现了三次。如果⽤递归来求解，fib(2)就会被计算三次，⽽⽤DP（Dynamic Programming）动态规划，则fib(2)只会计算⼀次，其他两次则是通过“查表”直接求得。⽽且，更关键的是：查求得该问题的解之后，
就不需要再继续去分解该问题了。⽽对于递归，是不断地将问题解，直到分解为基准问题（fib(0)或者fib(1)）
说了这么多，还是写下最长公共⼦序列的递归式才完整。
C[i,j]表⽰：(x1,x2,...,xi)和(y1,y2,...,yj)的最长公共⼦序列的长度。公式的具体解释可参考《算法导论》动态规划章节
三、LCS Python代码实现
#! /usr/bin/env python3
# -*- coding:utf-8 -*-
# Author  : mayi
# Blog  : wwwblogs/mayi0312/
# Date  : 2019/5/16
# Name  : test03
# Software : PyCharm
# Note  : ⽤于实现求解两个字符串的最长公共⼦序列
def longestCommonSequence(str_one, str_two, case_sensitive=True):
"""
str_one 和 str_two 的最长公共⼦序列
:param str_one: 字符串1
:param str_two: 字符串2（正确结果）
:param case_sensitive: ⽐较时是否区分⼤⼩写，默认区分⼤⼩写
:
return: 最长公共⼦序列的长度
"""
len_str1 = len(str_one)
len_str2 = len(str_two)
# 定义⼀个列表来保存最长公共⼦序列的长度，并初始化
record = [[0 for i in range(len_str2 + 1)] for j in range(len_str1 + 1)]
for i in range(len_str1):
for j in range(len_str2):
if str_one[i] == str_two[j]:
record[i + 1][j + 1] = record[i][j] + 1
elif record[i + 1][j] > record[i][j + 1]:
record[i + 1][j + 1] = record[i + 1][j]
else:
record[i + 1][j + 1] = record[i][j + 1]
return record[-1][-1]
if __name__ == '__main__':
# 字符串1
s1 = "BDCABA"
# 字符串2
s2 = "ABCBDAB"
# 计算最长公共⼦序列的长度
res = longestCommonSequence(s1, s2)
# 打印结果
print(res) # 4
以上就是本⽂的全部内容，希望对⼤家的学习有所帮助，也希望⼤家多多⽀持。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。