【LeetCode】5. 最长回文子串

1 题目

这题和有一题好像，也是回文子串相关题。

2 思想

dp相关题

• dp[i,j]表示 s[i,j] 是否是回文串
• 在上述基础上我们只需要判断 dp[i+1,j+1] 是否是回文串即可，于是便得递推式。
• 最后再双重for循环找一下最长的串

3 代码

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[0]*len(s) for i in range(len(s))]
        n = len(s)
        for i in range(n):
            dp[i][i] = 1 # 自身是回文串
        for span in range(2,n+1): # 区间长度从2开始
            for left in range(0,n-span+1):                
                right = left+span -1
                if s[left] == s[right]: # 如果两个字符相等
                    if left +1 == right:
                        dp[left][right] = 1
                    elif dp[left+1][right-1] :
                        dp[left][right] = 1        
        res = s[0]
        max_len = 1
        for i in range(n):
            for j in range(i+1,n):
                if dp[i][j] == 1:
                    if j-i+1 > max_len:
                        res = s[i:j+1]
                        max_len = j-i+1
        # print(dp)
        return res