经典题目（2）：最长公共子序列；最长公共子串

题目一：

给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列

数据范围：0≤∣str1∣,∣str2∣≤20000≤∣str1∣,∣str2∣≤2000

要求：空间复杂度 O(n2)，时间复杂度 O(n2)

方法：

公共子序列和公共子串的区别在于，公共子序列的字母或数字不一定靠在一起。

使用动态规划的方法来解决这个问题，初始化一个(m+1)行(n+1)列的dp数组（考虑字符串为空的情况，因为字符串只有一个字母或数字的时候要用到），遍历dp数组的时候（i,j），如果新遍历到的字符串对应位置的字符相等，则在旧遍历字符串基础上加一，如果新遍历到的字符串对应位置的字符不相等，则考虑dp[i][j-1]和dp[i-1][j]中的大值。

得到子序列的过程是从后向前遍历的，如果两个字符串对应位置的字符相等，就加到res中，如果不相等，就比较dp数组dp[i][j-1]和dp[i-1][j]，哪个大就往哪个方向后退一步。

代码：

class Solution: def LCS(self , s1: str, s2: str) -> str: # write code here if not s1 or not s2: return '-1' # 考虑特殊情况 m=len(s1) n=len(s2) dp=[[0]*(m+1) for _ in range(n+1)] #n+1行2 m+1列1 for i in range(1,m+1): for j in range(1,n+1): if s1[i-1]==s2[j-1]: # 注意 dp 和 s1s2的对应关系 dp[j][i]=dp[j-1][i-1]+1 else: dp[j][i]=max(dp[j-1][i],dp[j][i-1]) res=[] i=m j=n while i>0 and j>0: if s1[i-1]==s2[j-1]: res.append(s1[i-1]) i-=1 j-=1 elif dp[j-1][i]>dp[j][i-1]: j-=1 else: i-=1 return ''.join(reversed(res)) if res else '-1'

题目二：

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

数据范围： 1≤∣str1∣,∣str2∣≤50001≤∣str1∣,∣str2∣≤5000
要求： 空间复杂度 O(n2)，时间复杂度 O(n2)

方法：

动态规划的方法和最长公共子序列相似，但是由于子序列和子串的特性不同，如果新遍历到的字符串对应位置的字符不相等，直接重置为0。不过动态规划的方法用python可能会出现超时的问题，所以可以考虑用滑动窗口的方法

代码：

class Solution: def LCS(self , str1: str, str2: str) -> str: # write code here if len(str1)<len(str2): str1,str2=str2,str1 # 将更长的字符串作为str1 maxlen=0 res='' for i in range(len(str1)): if str1[i-maxlen:i+1] in str2: # str1[0:0] 会返回一个空字符串 '' res=str1[i-maxlen:i+1] maxlen+=1 return res