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

题目一给定两个字符串str1和str2输出两个字符串的最长公共子序列。如果最长公共子序列为空则返回-1。目前给出的数据仅仅会存在一个最长的公共子序列数据范围0≤∣str1∣,∣str2∣≤20000≤∣str1∣,∣str2∣≤2000要求空间复杂度 O(n2)时间复杂度 O(n2)方法公共子序列和公共子串的区别在于公共子序列的字母或数字不一定靠在一起。使用动态规划的方法来解决这个问题初始化一个(m1)行(n1)列的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 # 考虑特殊情况 mlen(s1) nlen(s2) dp[[0]*(m1) for _ in range(n1)] #n1行2 m1列1 for i in range(1,m1): for j in range(1,n1): 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[] im jn while i0 and j0: 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,str2str2,str1 # 将更长的字符串作为str1 maxlen0 res for i in range(len(str1)): if str1[i-maxlen:i1] in str2: # str1[0:0] 会返回一个空字符串 resstr1[i-maxlen:i1] maxlen1 return res