题目
Given a string s
, return the longest palindromic substring in s
.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Constraints:
1 <= s.length <= 1000
s
consist of only digits and English letters.
思路
遍历序列,求出所有可能的最大回文串,随后返回最大的一个。
代码
python版本:
class Solution:
def longestPalindrome(self, s: str) -> str:
res = ''
maxn = 0
def maxPalindromeLen(i):
nonlocal res, maxn
n = 1
while i-n >= 0 and i+n < len(s) and s[i-n] == s[i+n]:
n += 1
if 2*n-1 > maxn:
maxn = 2*n-1
res = s[i-n+1:i+n]
n = 0
while i-n >= 0 and i+n+1 < len(s) and s[i-n] == s[i+1+n]:
n += 1
if 2*n > maxn:
maxn = 2*n
res = s[i-n+1:i+n+1]
[maxPalindromeLen(i) for i in range(len(s))]
return res