首先考虑最长公共子序列的问题
递归解：
memo[(i,j)] 存放的是 s[i:] p[j:] 两个字符串的公共子序列
递归的思想是当前的两个字符相等了 只需要去看后面的字符串的情况
忘右边看
class Solution:
def LongCommonSubSequence(self, s, p):
memo = {}
def dp(i, j):
if (i, j) not in memo:
if i == len(s) or j == len(p): # 初始解
res = 0
else:
if s[i] == p[j]: # 当前两个位置字符相同 先加1 继续考察后面的字符
res = 1 + dp(i + 1, j + 1)
else:
res = max(dp(i + 1, j), dp(i, j + 1))
memo[(i, j)] = res
return memo[(i, j)]
return dp(0, 0)
对比一下相应的DP解
memo[i][j]表示s[:i] 和 p[:j]的最长公共子序列的长度
DP的思想是当前的字符相同了 我需要结合当前字符串的前面的字符串的情况来判断我整体的情况
往左边看
class Solution_DP:
def longestCommonSubsequence(self, s, p):
if not s or not p:
return 0
memo = [[0] * (len(s) + 1) for j in range(len(p) + 1)] # 初始解
for i in range(1, len(p) + 1): # memo的坐标比字符串的大1
for j in range(1, len(s) + 1):
if s[j - 1] == p[i - 1]: # memo的坐标比字符串的大1
memo[i][j] = memo[i - 1][j - 1] + 1
else:
memo[i][j] = max(memo[i][j - 1], memo[i - 1][j])
return memo[-1][-1]
接下来是最长公共子串
memo[i][j] 表示s1[:i] s2[:j]的两个子串的公共子串长度
限制条件是当前公共子串是以i j结尾的
使用了EndHere的思想 因为最长连续子串的终点可以分类讨论 假设最长的子串的终点是i 那么i一定在[0,len(s1)]范围内 全局最大解就是这些解（这么多种情况下）中的最大值
还记得之前说的连续子序列优化问题 基本上都可以使用endHere的思想吗？
def find_lcsubstr_(s1, s2):
memo = [[0]*(len(s2) + 1) for j in range(len(s1) + 1)]
res = 0 # 最长匹配的长度
for i in range(len(s1)):
for j in range(len(s2)):
if s1[i] == s2[j]:
memo[i + 1][j + 1] = memo[i][j] + 1 # 此时ij定义为前一个解的index 其范围就是[0, len(s1)] 写起来简单一点
res = max(res, memo[i+1][j+1])
return res
改一下 就可以输出子串是啥
def find_lcsubstr(s1, s2):
memo = [[0]*(len(s2) + 1) for j in range(len(s1) + 1)] # 生成0矩阵，为方便后续计算，比字符串长度多了一列
res = 0 # 最长匹配的长度
p = 0 # 最长匹配对应在s1中的最后一位
for i in range(len(s1)):
for j in range(len(s2)):
if s1[i] == s2[j]:
memo[i + 1][j + 1] = memo[i][j] + 1
res = max(res, memo[i+1][j+1])
if memo[i + 1][j + 1] > res:
res = memo[i + 1][j + 1]
p = i + 1
return s1[p - res:p], res # 返回最长子串及其长度
最长公共子串的递归解还是有点难写
自己写了一份 效率很低 TODO
class Solution:
def mxcommon(self, s, p):
def dp(i, j, sta):
if i == len(s) or j == len(p):
return 0
else:
if sta:
return 1 + dp(i + 1, j + 1, 1) if s[i] == p[j] else 0
if s[i] == p[j]: # 后面的字符串必须强制连续
res = max(1 + dp(i + 1, j + 1, 1), dp(i + 1, j + 1, 0)) # 当前位置+1 and 后面强制连续 or
else:
res = max(dp(i + 1, j, 0), dp(i, j + 1, 0))
return res
return dp(0, 0, 0)
网友评论