题解 | #最长公共子串#

1. 描述
2. 给定两个字符串str1和str2,输出两个字符串的最长公共子串
3. 题目保证str1和str2的最长公共子串存在且唯一。
5. 数据范围： 1 \le |str1|,|str2| \le 50001≤∣str1∣,∣str2∣≤5000
6. 要求： 空间复杂度 O(n^2)O(n
7. 2
8. )，时间复杂度 O(n^2)O(n
9. 2
10. )
11. 示例1
12. 输入：
13. "1AB2345CD","12345EF"
14. 复制
15. 返回值：
16. "2345"

这个题目使用滑窗的思路 就是 以最长的 str1字符串为操作主题，然后设置左指针，当前选取的字符如果在这个st2中则 i顺延一位， left做指针不变，就可以。

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