本文最后更新于: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
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
class Solution:
def minWindow(self, s: str, t: str) -> str:
target_dict = dict()
for char in t:
if char not in target_dict:
target_dict[char]=0
target_dict[char] += 1

min_length = 1e7
min_str = ""

left = 0
right = 0

cur_dict = dict()
for key in target_dict.keys():
cur_dict[key] = []

def update_left(cur_dict, target_dict):
min_pos = 1e7
get = True
for key in target_dict.keys():
if len(cur_dict[key]) < target_dict[key]:
get = False
if cur_dict[key]:
min_pos = min(min_pos, cur_dict[key][0])
return min_pos, get

while right < len(s):
char = s[right]
if char not in target_dict:
right += 1
else:
cur_dict[char].append(right)
if len(cur_dict[char]) > target_dict[char]:
cur_dict[char].pop(0)
min_pos, get = update_left(cur_dict, target_dict)
if min_pos < 1e7:
left = min_pos
if get:
cur_str = s[left:right + 1]
if len(cur_str) < min_length:
min_length = len(cur_str)
min_str = cur_str
right += 1
return min_str

49. 字母异位词分组

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res_dict = dict()

for str_data in strs:
key = ''.join(sorted(list(str_data)))
if key not in res_dict:
res_dict[key] = []
res_dict[key].append(str_data)

return [item for item in res_dict.values()]

参考资料



文章链接:
https://www.zywvvd.com/notes/study/algorithm/string/str-lcs/str-lcs/


“觉得不错的话,给点打赏吧 ୧(๑•̀⌄•́๑)૭”

微信二维码

微信支付

支付宝二维码

支付宝支付

最长公共子串 / 子序列
https://www.zywvvd.com/notes/study/algorithm/string/str-lcs/str-lcs/
作者
Yiwei Zhang
发布于
2022年7月12日
许可协议