目录

力扣-查询两个字符串的最长公共子串

耗子收录于刷题

2022-12-05 约 388 字预计阅读 1 分钟

目录

查询两个字符串的最长公共子串。

用 Python 实现查找两个字符串 a,b 中的最长公共子串¹
Python——查询两个字符串的最长公共子串²

循环查找

思路：

通过字符串1从全长开始判断是否存在于字符串2中，如果不存在则迭代至只有1位字符
通过列表来保存结果，以免出现有多个同长的最长子串情况
选择长度短的字符串作为操作字符串，以提升效率

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


def getLongestSameStr(str1, str2):
    # 判断两个字符串长短，取短的那个进行操作
    if len(str1) > len(str2):
        str1, str2 = str2, str1

    f = []
    for i in range(len(str1), 0, -1):
        for j in range(len(str1) + 1 - i):
            e = str1[j:j + i]
            if e in str2:
                f.append(e)
        # 判断当前长度下，是否存在子串
        if f:
            break

    f1 = ",".join(f)
    return f1

滑动窗口

1
2
3
4
5
6
7
8
9


def LCS(str1: str, str2: str) -> str:
    res = ""
    left = 0
    for i in range(len(str1)+1):
        if str1[left:i+1] in str2:
            res = str1[left:i+1]
        else:
            left = left+1
    return res