5. Longest Palindromic Substring

描述

Example 1:

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

Example 2:

Input: "cbbd"
Output: "bb"

解法

每个字符从中间向两端扩展，直到不是回文串终止，记录最大长度的字符串。

class Solution:
    loc = 0
    max_len = 0

    def longestPalindrome(self, s: str) -> str:
        length = len(s)
        if length < 2:
            return s

        for i in range(length):
            self.extend_palindrome(s, i, i)      # for odd
            self.extend_palindrome(s, i, i+1)    # for even

        return s[self.loc: self.loc + self.max_len]

    def extend_palindrome(self, s, l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1

        if self.max_len < r - l - 1:
            self.loc = l + 1
            self.max_len = r - l - 1

时间复杂度 $O(N^2)$

空间复杂度 $O(1)$

引用