Leetcode.5 最长回文子串 （快手面试题）

题目链接：5. 最长回文子串 - 力扣（LeetCode）

题目描述：

给你一个字符串 s，找到 s 中最长的 回文子串

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

解题思路：动态规划

具体可参考，求回文子串章节内容    链接：CSDN

本题在以上基础上增加了 指针start 标记回文子串的开始和max_len表示最长的回文子串长度

每次判断为回文子串时，与最长回文子串进行比较，若长度更长，则更新起始指针与长度

代码实现：

class Solution:def longestPalindrome(self, s: str) -> str:# 定义dp数组dp = [[False for _ in range(len(s))] for _ in range(len(s))]max_len = 0start = 0for i in range(len(s)-1,-1,-1):for j in range(i,len(s)):if s[i] == s[j]:if j - i <= 1:dp[i][j] = Trueif max_len < j-i+1:max_len = j -i +1start = ielif dp[i+1][j-1]:dp[i][j] = Trueif max_len < j - i +1:max_len = j -i +1start = ireturn s[start:max_len+start]