本文最后更新于:2024年5月7日 下午
本文记录寻找两个字符串最长公共子串和子序列的方法。
名词区别
- 最长公共子串(Longest Common Substring)与最长公共子序列(Longest Common Subsequence)的区别: 子串要求在原字符串中是连续的,而子序列则只需保持相对顺序,并不要求连续。
最长公共子串
-
是指两个字符串中最长连续相同的子串长度。
例如:str1=“1AB2345CD”,str2=”12345EF”,则str1,str2的最长公共子串为2345。
动态规划
-
如果
str1
的长度为 $N$,str2
的长度为 $M$,生成大小为 $N*M$ 的 数组 $dp$ , $dp[i][j]$表示 $str1[0…i]$ 与 $str2[0…j]$ 的最长公共子串的长度。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
def find_lcsubstr(s1: str, s2: str):
"""
Longest Common Substring
最长公共子串 (连续串, 非序列)
O(mn)
Args:
s1 (str): string 1
s2 (str): string 2
Returns:
str: longest_sub_string, max_length
"""
s1 = str(s1)
s2 = str(s2)
# 生成0矩阵,为方便后续计算,比字符串长度多了一列
m = np.zeros([len(s1) + 1, len(s2) + 1], dtype='uint16')
mmax = 0 # 最长匹配的长度
p = 0 # 最长匹配对应在s1中的最后一位
for i in range(len(s1)):
for j in range(len(s2)):
if s1[i] == s2[j]:
m[i+1][j+1] = m[i][j] + 1
if m[i+1][j+1] > mmax:
mmax = m[i+1][j+1]
p = i+1
return s1[p-mmax:p], mmax # 返回最长子串及其长度 -
该算法:
- 时间复杂度 $O(MN)$
- 空间复杂度 $O(MN)$
优化空间复杂度
- 经典动态规划的方法需要大小为$M*N$的$ dp$ 矩阵,但实际上是可以减少至$O(1)$的,因为计算每一个$dp[i][j]$的时候只需要计算$dp[i-1][j-1]$,所以按照斜线方向计算所有的值,只需要一个变量就可以计算。
最长公共子序列
-
子串要求字符必须是连续的,但是子序列就不是这样。
最长公共子序列是一个十分实用的问题,它可以描述两段文字之间的“相似度”,即它们的雷同程度,从而能够用来辨别抄袭。对一段文字进行修改之后,计算改动前后文字的最长公共子序列,将除此子序列外的部分提取出来,这种方法判断修改的部分,往往十分准确。
-
解法就是用动态回归的思想,一个矩阵记录两个字符串中匹配情况,若是匹配则为左上方的值加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
38
39
40
41
42
43
44
45
46
47
48
def find_lcseque(s1: str, s2: str):
"""
Longest Common Subsequence
最长公共子序列(不一定连续)
O(mn)
Args:
s1 (str): string 1
s2 (str): string 2
Returns:
str: Subsequence_str
"""
# 生成字符串长度加1的0矩阵,m用来保存对应位置匹配的结果
m = np.zeros([len(s1)+1, len(s2)+1], dtype='uint16')
# d用来记录转移方向
d = np.zeros([len(s1)+1, len(s2)+1], dtype='uint8')
for p1 in range(len(s1)):
for p2 in range(len(s2)):
if s1[p1] == s2[p2]: # 字符匹配成功,则该位置的值为左上方的值加1
m[p1+1][p2+1] = m[p1][p2]+1
d[p1+1][p2+1] = 1
elif m[p1+1][p2] > m[p1][p2+1]: # 左值大于上值,则该位置的值为左值,并标记回溯时的方向
m[p1+1][p2+1] = m[p1+1][p2]
d[p1+1][p2+1] = 2
else: # 上值大于左值,则该位置的值为上值,并标记方向up
m[p1+1][p2+1] = m[p1][p2+1]
d[p1+1][p2+1] = 3
(p1, p2) = (len(s1), len(s2))
s = []
while m[p1][p2]: # 不为None时
c = d[p1][p2]
if c == 1: # 匹配成功,插入该字符,并向左上角找下一个
s.append(s1[p1-1])
p1 -= 1
p2 -= 1
if c == 2: # 根据标记,向左找下一个
p2 -= 1
if c == 3: # 根据标记,向上找下一个
p1 -= 1
s.reverse()
return ''.join(s) -
该算法:
- 时间复杂度 $O(MN)$
- 空间复杂度 $O(MN)$
76. 最小覆盖子串
给你一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s
中不存在涵盖 t
所有字符的子串,则返回空字符串 ""
。
注意:
- 对于
t
中重复字符,我们寻找的子字符串中该字符数量必须不少于t
中该字符数量。 - 如果
s
中存在这样的子串,我们保证它是唯一的答案。
1 |
|
49. 字母异位词分组
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
1 |
|
参考资料
文章链接:
https://www.zywvvd.com/notes/study/algorithm/string/str-lcs/str-lcs/
“觉得不错的话,给点打赏吧 ୧(๑•̀⌄•́๑)૭”
微信支付
支付宝支付