5. Longest Palindromic Substring

# 5. Longest Palindromic Substring

## 刷题内容

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

## 解题方案

- 时间复杂度: O(N^2)- 空间复杂度: O(N^2)

dp[i][j]代表s[i:j+1]是否是parlindrome

class Solution:
def longestPalindrome(self, s: str) -> str:
res = ''
dp = [[False] * len(s) for i in range(len(s))]
for i in range(len(s)-1, -1, -1):
for j in range(i, len(s)):
dp[i][j] = (s[i] == s[j]) and (j - i < 3 or dp[i+1][j-1])
if dp[i][j] and (j - i + 1 > len(res)):
res = s[i:j+1]
return res

- 时间复杂度: O(N^2)- 空间复杂度: O(1)

1. 奇数：'xxx s[i] xxx', 比如 'abcdcba'
2. 偶数：'xxx s[i] s[i+1] xxx', 比如 'abcddcba'

beats 58.44%

python
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
l = 0 # left index of the current substring
r = 0 # right index of the current substring
max_len = 0 # length of the longest palindromic substring for now
n = len(s)
for i in range(n):
# odd case: 'xxx s[i] xxx', such as 'abcdcba'
for j in range(min(i+1, n-i)): # 向左最多移动 i 位，向右最多移动 (n-1-i) 位
if s[i-j] != s[i+j]: # 不对称了就不用继续往下判断了
break
if 2 * j + 1 > max_len: # 如果当前子串长度大于目前最长长度
max_len = 2 * j + 1
l = i - j
r = i + j

        # even case: 'xxx s[i] s[i+1] xxx', such as 'abcddcba'
if i+1 < n and s[i] == s[i+1]:
for j in range(min(i+1, n-i-1)): # s[i]向左最多移动 i 位，s[i+1]向右最多移动 [n-1-(i+1)] 位
if s[i-j] != s[i+1+j]: # 不对称了就不用继续往下判断了
break`