最长公共子串 / 子序列

本文最后更新于：2023年8月18日晚上

本文记录寻找两个字符串最长公共子串和子序列的方法。

名词区别

最长公共子串（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]$ 的最长公共子串的长度。


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，否则为左方和上方的最大值。一个矩阵记录转移方向，然后根据转移方向，回溯找到最长子序列。


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 中存在这样的子串，我们保证它是唯一的答案。

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. 字母异位词分组

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

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

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()]