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(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%

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
                    if 2 * j + 2 > max_len:
                        max_len = 2 * j + 2
                        l = i - j
                        r = i + 1 + j
        return s[l:r+1]
top Created with Sketch.