最长公共子串
问题简述
给定两个字符串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
有一个超长用例导致上面的代码超时；
下面是另一种实现方式，本质上跟动态规划的思路是一样的；
Last updated