算法刷题Day28:BM66 最长公共子串
题目链接，点击跳转
题目描述：
解题思路：
方法一：暴力枚举
- 遍历
str1的每个字符x，并在str2中寻找以相同元素x为起始的最长字符串。 - 记录最长的公共子串及其长度。
代码实现：
def LCS(self, str1: str, str2: str) -> str:
len1 = len(str1)
len2 = len(str2)
max_start = 0
max_end = 0
max_length = 0
for i in range(len1):
for j in range(len2):
if str2[j] == str1[i]:
pos1 = i
pos2 = j
length = 0
while pos1 < len1 and pos2 < len2 and str1[pos1] == str2[pos2]:
length += 1
pos1 += 1
pos2 += 1
if length > max_length:
max_length = length
max_start = j
max_end = pos2
return str2[max_start:max_end]
分析：
时间复杂度：O(n \* m \* min(n, m))，其中 n 和 m 分别是两个字符串的长度。
空间复杂度：O(1)。
缺点：时间复杂度过高，在字符串较长时会超时。
方法二：动态规划
- 使用一个二维数组来记录子串长度
- 状态转移方程
如果str1[i-1] == str2[j-1]，则dp[i][j] = dp[i-1][j-1] +1
如果str1[i-1] != str2[j-1]，则dp[i][j] = 0
代码实现：
def LCS(self, str1: str, str2: str) -> str:
len1 = len(str1)
len2 = len(str2)
max_end = 0
max_length = 0
dp = [[0 for _ in range(len2 + 1)] for _ in range(len1 + 1)]
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > max_length:
max_end = j
max_length = dp[i][j]
else:
dp[i][j] = 0
return str2[max_end - max_length:max_end]
时间复杂度：O(n \* m)，其中 n 和 m 分别是两个字符串的长度。
空间复杂度：O(n \* m)。
缺点：python版本会超时
方法三：滑动窗口
1.遍历较长的字符串，判断窗口内的字符，是否存在于在另一个字符串中。
代码实现
def LCS(self, str1: str, str2: str) -> str:
if len(str1) < len(str2):
str1, str2 = str2, str1
res = ""
max_len = 0
for i in range(len(str1)):
if str1[i - max_len:i + 1] in str2:
res = str1[i - max_len:i + 1]
max_len += 1
return res
时间复杂度：O(n\*k\*m)。其中 n 是较长字符串的长度。k 是切片长度，最多为 n。使用 in 判断是否存在于 str2 中，其时间复杂度为 O(m)，其中 m 是 str2 的长度。