最长公共子串

最长公共子串_牛客题霸_牛客网

问题简述

给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。 

思路1：动态规划（超时）

• 定义 dp(i, j) 表示以 s1[i - 1] 和 s2[j - 1] 结尾的最长公共子串；

  • 注意：dp(i, j) 保存的并不是全局最优解，所以需要用全局变量来动态更新；

  • 本题中，因为需要返回具体子串，所以可以保存两个变量，一个是结尾索引，一个是子串长度，根据这两个变量就可以找到具体的公共子串；

• 初始化 i == 0 or j == 0 时，dp(i, j) == 0

• 转移方程：dp(i, j) = dp(i - 1, j - 1) + 1 if s1[i - 1] == s2[j - 1] else 0；

  • 值得注意的是，当前状态 (i, j) 只跟 (i-1, j-1) 状态有关，这与常见的双样本位置对应模型不同（比如“编辑距离”）；

  • 具体来说，状态转移时没有用到 (i, j-1) 和 (i-1, j)，但它们依然是要计算的，这在迭代写法中是自然的；但是在递归写法中很容易被忽略（因为转移方程中没有它们），详见递归写法的代码；

写法1）递归

class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        # write code here
        import sys
        sys.setrecursionlimit(100000)
        from functools import lru_cache
        
        self.mLen = 0
        self.end = 0
        
        @lru_cache(maxsize=None)
        def dp(i, j):
            if i == 0 or j == 0: return 0
            # 可以省略
            # if i == 1: return int(s1[0] == s2[j - 1])
            # if j == 1: return int(s1[i - 1] == s2[0])

            # 虽然没有用到这两个状态的值，但依然要调用，这是递归写法很容易忽略的点
            _ = dp(i - 1, j)
            _ = dp(i, j - 1)
            r = dp(i - 1, j - 1) + 1 if s1[i - 1] == s2[j - 1] else 0
            # 更新全局最优解
            if r > self.mLen:
                self.mLen = r
                self.end = i
            return r
        
        dp(len(s1), len(s2))
        return s1[self.end - self.mLen: self.end]

写法2）迭代（从递归修改而来）

class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        
        mLen = 0
        end = 0
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # 可以省略
                # if i == 0 or j == 0:
                #     dp[i][j] = 0
                dp[i][j] = dp[i - 1][j - 1] + 1 if s1[i - 1] == s2[j - 1] else 0
                if dp[i][j] > mLen:
                    mLen = dp[i][j]
                    end = i

        return s1[end - mLen: end]

思路2

• 有一个超长用例导致上面的代码超时；

• 下面是另一种实现方式，本质上跟动态规划的思路是一样的；

Python

class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        
        ret = ''
        mLen = 0
        
        for i in range(len(s1)):  # 遍历每一个 s1[:i + 1] 子串
            sub = s1[i - mLen: i + 1]  # 截取可能的最长公共子串
            if sub in s2:  # 如果是公共子串
                ret = sub  # 保存结果
                mLen += 1  # 尝试更长的子串
        
        return ret