最长公共子串LCS

描述

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

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

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

暴力解法：枚举法

基本思路

枚举法是最直观的暴力解法，通过比较所有可能的子串组合来找到最长的公共子串。

具体实现步骤

  1. 遍历所有起始位置：
  • 遍历 str1 的每个字符作为子串的起始位置 i。
  • 遍历 str2 的每个字符作为子串的起始位置 j。
  1. 扩展子串：
  • 从 i 和 j 开始，逐个字符比较 str1 和 str2。
  • 如果字符相等，则继续向后比较，增加当前子串长度。
  • 如果字符不等，则停止扩展，记录当前子串长度。
  1. 维护最大值：
  • 在每次找到公共子串时，比较其长度与当前最大值，更新最大值及其位置。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def longest_common_substring(str1, str2):
    max_len = 0
    end_pos = 0  # 记录最长子串在str1中的结束位置
    
    for i in range(len(str1)):
        for j in range(len(str2)):
            k = 0
            while (i + k < len(str1) and j + k < len(str2) 
                   and str1[i + k] == str2[j + k]):
                k += 1
            if k > max_len:
                max_len = k
                end_pos = i + k
    
    return str1[end_pos - max_len : end_pos] if max_len > 0 else ""

时间复杂度分析

  • 最坏情况：两个字符串完全不相同，每次比较都需要遍历到字符串末尾。
  • 外层循环：O(n)（str1 的长度）
  • 内层循环：O(m)（str2 的长度）
  • 内层 while 循环：最坏O(min(n, m))
  • 总时间复杂度：O(n * m * min(n, m)) ≈ O(n^3)（当 n ≈ m 时）

空间复杂度

  • 额外空间：仅使用了常数空间（max_len 和 end_pos），因此空间复杂度为 O(1)。

动态规划（DP）：O(n²)

定义一个dp表，表示局部最长公共子串长度（从末尾开始到开头，也就是最后一个公共子串长度，如果有多个，必须是末尾元素开始的那个，如果末尾开始没有则为0，这样变结尾后就能每次都统计局部最长公共子串长度，最终得到全局的所有局部最长子串长度）

  • dp[i][j] 的定义：
    • 表示 以 str1[i-1] 和 str2[j-1] 结尾的公共子串的长度（注意不是全局最长）。
    • 例如：dp[3][3] = 2 表示 str1[0:3] 和 str2[0:3] 的末尾有长度为 2 的公共子串。
      具体怎么做？
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      class Solution:
          def LCS(self , str1: str, str2: str) -> str:
              height, width = len(str1), len(str2)
      		# 初始化dp表
              dp = [[0] * (width+1) for _ in range(height+1)] # +1
              max_len = 0
              max_suffix_index_s1 = 0
              for i in range(1,height+1):
                  for j in range(1,width+1):
                      if str1[i-1]==str2[j-1]:
                          dp[i][j] = dp[i-1][j-1]+1
                          if dp[i][j]>max_len:
                              max_len = dp[i][j]
                              max_suffix_index_s1 = i
                      else:
                          dp[i][j] = 0
              
              return str1[max_suffix_index_s1-max_len:max_suffix_index_s1]

后缀自动机（SAM）： O(n)

奇怪的想法：
给定字符串a和字符串b，两个指针分别指向a和b，当匹配到相同字符后，让a+k,b+k，k表示匹配到的长度，当匹配到不同字符后，记录b’=b+k即可，接下来只需要让a++来匹配b’的位置，因为如果这个位置匹配不到，说明长度不及k，（但是和匹配k=0位置有什么区别吗？）匹配到了依然需要全部匹配，如果匹配不到还是很难处理，但是如果0和b‘匹配不到中间就不用匹配了，如果从0、1依次匹配就还要匹配，因为能直接获得长度相关的信息

字典解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from collections import defaultdict
class Solution:
    def LCS(self , str1: str, str2: str) -> str:
            if not str1 or not str2:
                return ""
            
            # 构建str2的字符位置索引
            char_positions = defaultdict(list)
            for idx, char in enumerate(str2):
                char_positions[char].append(idx)
            
            # 使用字典存储状态：key=当前索引，value=连续匹配长度
            dp = {}
            max_len = 0
            end_pos = 0  # 记录在str1中的结束位置
            
            for i, char in enumerate(str1):
                new_dp = {}
                # 只处理当前字符在str2中实际出现的位置
                for j in char_positions[char]:
                    # 检查前一个位置是否连续
                    if j > 0 and j - 1 in dp:
                        length = dp[j - 1] + 1
                    else:
                        length = 1
                    
                    new_dp[j] = length
                    
                    # 更新全局最大值
                    if length > max_len:
                        max_len = length
                        end_pos = i
                
                dp = new_dp  # 更新状态
            
            start = end_pos - max_len + 1
            return str1[start:end_pos + 1] if max_len > 0 else ""

最长公共子序列

最长公共子串很好理解，无非就是共同的最长句子，公共子序列表示：两个字符串有序、可以零散选出的字符组成的序列，案例：

示例1

输入：
"1A2C3","B1D23"
返回值：
"123456"

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
    def LCS(self, s1: str, s2: str) -> str:
        height, width = len(s1), len(s2)
        # corner case handling:
        if height==0 or width==0:
            return "-1"

		# 初始化dp表
        dp = [[0] * (width+1) for _ in range(height+1)] # +1
        max_length = 0
	    
	    # # 填充长度记录dp表没有必要，因为已经初始化为0了
        # for i in range(height):
        #     dp[i][0] = 0
        # for i in range(width):
        #     dp[0][i] = 0
        for i in range(1, height+1):# +1
            for j in range(1, width+1):# +1
                if s1[i-1] == s2[j-1]: # 不是s1[i] == s2[j]
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    
                    if dp[i][j] > max_length:
                        max_length = dp[i][j]
                else:
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
        
        # 恢复子序列
        lcs = []
        i,j=height,width
        while dp[i][j]>0 :
            if s1[i-1] ==s2[j-1]:
                lcs.append(s1[i-1])
                i-=1
                j-=1
            elif dp[i-1][j]==dp[i][j]:
                i-=1
            else:
                j-=1
        return ''.join(reversed(lcs)) if lcs else "-1"

初始化思路

每个元素dp[i][j]依赖左上dp[i-1][j-1]、正上方dp[i-1][j]或正左方dp[i][j-1]的元素,可以直接初始化i=0和j=0的元素为0，然后从i=1开始一行一行计算，每行循环中列也从j=1开始

填充思路

将以s1[:i]和s2[:j]的LCS求解问题分解成三个子问题：

  1. 最后一个字符匹配，前面的串字符之间互相匹配
  2. s1[i]和s2[:j-1]部分中的字符匹配，s2[j]和s1[:i]都不匹配或者相同字符用完，如果匹配，存在dp[i][j]=dp[i][j-1]？？？
    如果两个字符串最后一个位置相等，说明整体长度在原先加1，否则？？只可能来自

恢复思路

如果最后一个字符相同，则直接增加，并且减一；否则化为子问题

dp[i][j]==dp[i-1][j-1]+1不是必要条件

常见浅拷贝问题

在二维数组初始化时，不能使用两个乘法而是一个乘法，否则第二个维度只是1d数组的简单引用，导致修改每个列表都会影响别的列表，错误写法❌：

1
dp = [[0] * (width+1)] * (height+1)

正确写法✔：

1
dp = [[0] * (width+1) for _ in range(height+1)]

数组长度以及含义问题

dp数组表示的不是i,j结尾，而是i-1,j-1结尾！！而i=0 or j=0时只是辅助计算的部分；
依次遍历行即可，不要斜着遍历，无需手动i，j增加

1
2
3
4
5
6
7
8
9
# 1.
dp = [[0] * (width+1) for _ in range(height+1)] # 别忘了+1

# 2.
for i in range(1, height+1):# +1
	for j in range(1, width+1):# +1
		if s1[i-1] == s2[j-1]: # 不是s1[i] == s2[j]

#