子串 子序列 总结

最长公共子串

子串的要求比子序列严格，所以可以讨论子串的终点

def longestCommonSubsequence_(self, s, p):
    if not s or not p:
        return 0
    res = 0
    dp = [[0]*(len(p)+1) for _ in range(len(s)+1)]
    for i in range(1, len(s)+1): # 一定要注意坐标的定义
        for j in range(1, len(p)+1): # 这里的i,j定义的是dp数组的坐标 比字符串的坐标大1
            if s[i-1] == p[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
                res =  max(res, dp[i][j])
    return res

最长公共子序列

DP解

def longestCommonSubsequence(self, s, p):
    if not s or not p:
        return 0
    dp = [[0]*(len(p)+1) for _ in range(len(s)+1)]
    for i in range(1, len(s)+1): # 一定要注意坐标的定义
        for j in range(1, len(p)+1): # 这里的i,j定义的是dp数组的坐标 比字符串的坐标大1
            if s[i-1] == p[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[-1][-1]

递归+memo

def LongCommonSubSequence_rec(self, s, p):
    memo = {}  # 定义memo[(i,j)] 是s[:i] p[:j] 右边是开区间 的最长子序列
    def dp(i, j):  # i，j是memo的坐标
        if (i, j) in memo:
            return memo[(i, j)]
        if i == 0 or j == 0: # 某一个字符串已经扫描完
            res = 0
        elif s[i - 1] == p[j - 1]:  # 字符串坐标比memo坐标小1
            res = 1 + dp(i - 1, j - 1)
        else:
            res = max(dp(i - 1, j), dp(i, j - 1))
        memo[(i, j)] = res
        return res
    return dp(len(s), len(p))

最长公共回文串

对称轴拓展法

def longestPalindrome(self, s):
    """
    :type s: str
    :rtype: str
    """
    self.res = ""
    def expandAroundCenter(left, right):
        l, r = left, right
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        if r - l - 1 > len(self.res):
            self.res = s[l + 1:r]
    for i in range(0, len(s)):
        expandAroundCenter(i, i)
        expandAroundCenter(i, i + 1)
    return self.res

DP解

def longestPalindrome(self, s):
    n = len(s)
    maxStr = ''
    DP = [[0] * n for _ in range(n)]  # 这么创建二维list 存放 的是实值不是引用
    for j in range(n):  # 终点
        for i in range(0, j + 1):  # 起点
            if (j - i < 2 or DP[i + 1][j - 1]) and s[i] == s[j]:  #包含两种情况 i,i i,i+1
                DP[i][j] = 1
            if DP[i][j] and j - i + 1 > len(maxStr):
                maxStr = s[i:j + 1]
    return maxStr

最长公共回文子序列

DP

def subSeq(self, s):
    dp = [[0] * len(s) for _ in range(len(s))]  # dp(i,j)定位为s[i,j]的最长回文子序列
    for i in range(len(s) - 1, -1, -1):  # 起点
        dp[i][i] = 1
        for j in range(i + 1, len(s)):  # 终点
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][-1]

递归+memo

def subSeq_rec(self, s):
    memo = {}

    def dp(i, j):  # 定义dp(i,j)为子串i到j中最大子序列
        if (i, j) in memo:
            return memo[(i, j)]
        if i == j:
            return 1
        elif s[i] == s[j]:
            if j - i == 1:
                return 2
            else:
                res = dp(i + 1, j - 1) + 2
        else:
            res = max(dp(i + 1, j), dp(i, j - 1))
        memo[(i, j)] = res
        return memo[(i, j)]

    return dp(0, len(s) - 1)