[数据结构与算法]leetcode 5.最长回文子数列——python

暴力解法

看到这道题是第一个想的是暴力求解的方法，我们设置两个变量，一个变量代表起始位置，初始量为0，另外一个代表的是长度，初始量为1，我们进行遍历，如果发现更长的回文数列，那么就调换位置，最后返回结果。
代码如下

# encoding:utf-8
def ff(a, b, c):# 判断是否为回文数列
    while b < c:
        if a[b] != a[c]:
            return False
        b += 1
        c -= 1
    return True

def f():
    s = input()
    lenS = len(s)
    if lenS < 2:
        return s
    maxlen = 1
    begin = 0
    s = list(s)

    for i in range(lenS-1):
        for j in range(i+1, lenS):
            if j-i+1 > maxlen and ff(s, i, j):
                maxlen = j-i+1
                begin = i
                # print(maxlen)
    return s[begin:begin+maxlen]

print(f())

动态规划求解

这道题其实动态规划也可以求解，首先我们进行判断，s长度小于2就不需要再计算了，如果大于二，我们还是先设置两个变量，同上。之后设置数列dp[i][j]来表示i~j是否为回文数列，之后我们开始进行计算，我们发现如果i，j是回文数列，那么i-1，j-1一定是的，所以i，j是回文数列的条件是i-1,j-1是和第i=第j，这就是状态转移方程，边界条件就是dp[i][i]一定是回文数列。
代码如下

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        
        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i..j] 是否是回文串
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        
        # 递推开始
        # 先枚举子串长度
        for L in range(2, n + 1):
            # 枚举左边界，左边界的上限设置可以宽松一些
            for i in range(n):
                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右边界越界，就可以退出当前循环
                if j >= n:
                    break
                    
                if s[i] != s[j]:
                    dp[i][j] = False 
                else:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                
                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]