给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
1
2
3
| 输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
|
示例 2：
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution:
def longestPalindrome(self, s: str) -> str:
str_len = len(s)
max_len = 1
start_index = 0
dp = [[0]*str_len for _ in range(str_len)]
for i in range(str_len):
dp[i][i] = 1
for j in range(str_len):
for i in range(j - 1, -1, -1):
if j == i+ 1 and s[j] == s[i]:
dp[i][j] = 2
if j > i+1 and dp[i+1][j-1] > 0 and s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
if dp[i][j] > max_len:
max_len = dp[i][j]
start_index = i
return s[start_index:start_index + max_len]
|