5. Longest Palindromic Substring

5. Longest Palindromic Substring

难度: Medium

刷题内容

原题连接

内容描述

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

Example 1:

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

Input: "cbbd"
Output: "bb"

解题方案

思路 1
- 时间复杂度: 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

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

回文字符串长度为奇数和偶数是不一样的:

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

我们区分回文字符串长度为奇数和偶数的情况,然后依次把每一个字符当做回文字符串的中间字符,向左右扩展到满足回文的最大长度,不停更新满足回文条件的最长子串的左右index: lr,最后返回s[l:r+1]即为结果

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
top Created with Sketch.