题目
给定一个字符串 s
,找到 s
中最长的回文子串。你可以假设 s
的最大长度为 1000。
示例 1:
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2:
输入: “cbbd”
输出: “bb”
方案一(中心拓展)
class Solution:
def expandAroundCenter(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return left + 1, right - 1
def longestPalindrome(self, s: str) -> str:
start, end = 0, 0
for i in range(len(s)):
left1, right1 = self.expandAroundCenter(s, i, i)
left2, right2 = self.expandAroundCenter(s, i, i + 1)
if right1 - left1 > end - start:
start, end = left1, right1
if right2 - left2 > end - start:
start, end = left2, right2
return s[start: end + 1]
-
方案二(动态规划)
class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) if n < 2: return s # 动态规划算法 # dp[i][j] 表示 s[i:j+1] 是否是回文串 dp = [[False] * n for _ in range(n)] for i in range(n): dp[i][i] = True start, end = 0, 0 # 递推公式,dp[i][j] = dp[i-1][j-1] and (s[i] == s[j]) # 注意填表顺序 for j in range(1, n): for i in range(j): if s[i] == s[j]: if j - i < 3: dp[i][j] = True else: dp[i][j] = dp[i+1][j-1] if dp[i][j]: if j - i > end - start: start = i end = j return s[start:end+1]
原文
https://leetcode-cn.com/explore/interview/card/2020-top-interview-questions/289/dynamic-programming/1293/
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/