最长公共子串最长公共子序列

首先考虑最长公共子序列的问题
递归解：
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)

最后编辑于：2019.04.14 22:04:22

最长公共子串 最长公共子序列

最长公共子串最长公共子序列