GoCalf Calf 的自留地 · 昙花一现

5. Longest Palindromic Substring

Problem

Given a string s, return the longest palindromic substring in s.

A string is palindromic if it reads the same forward and backward. A substring is a contiguous non-empty sequence of characters within a string.

https://leetcode.com/problems/longest-palindromic-substring/

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

Test Cases

python
class Solution:
    def longestPalindrome(self, s: str) -> str:
solution_test.py下载完整源码
py
import pytest

from solution import Solution


@pytest.mark.parametrize('s, expected', [
    ('babad', {'bab', 'aba'}),
    ('cbbd', 'bb'),

    ('x', 'x'),
    ('xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx', 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx')
])
class Test:
    def test_solution(self, s, expected):
        sol = Solution()
        res = sol.longestPalindrome(s)
        if isinstance(expected, str):
            assert res == expected
        else:
            assert res in expected

Thoughts

Palindromic string(回文)一定是按中间位置对称的。注意奇数长度和偶数长度的区别。

从左到右遍历每个字符,对于当前字符,检查以其为中心能够构成的最长的 palindromic(注意奇偶问题)。

  • 奇数长度的:以其为正中心。
  • 偶数长度的:以其及其右边相邻字符为中心。

时间复杂度比 O(n) 略高,但一般情况不会太高。

遍历时候大部分字符无法形成长于 1 的回文,判定所需的时间为常数。

假设这个字符串由 k 个长度为 m 的非平凡回文构成,k * m = n,那么大约需要做 k 次 O(m) 的判定,总计约 O(k * m) = O(n)。

连续的相同字符越多,时间复杂度越高。最差情况,字符串的 n 个字符全都一样,那么对于第 i 个字符,需要的时间大致为 O(min(i, n-i)),总共大约为 O(n²)。

所以最坏情况时间复杂度为 O(n²),但一般情况下,时间复杂度基本是 O(n)。

Code

py
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        longest = [1, 0] # [length, begin position]

        def find_palindromic(mid, odd):
            l, r = mid - (odd and 1 or 0), mid + 1
            while l >= 0 and r < n and s[l] == s[r]:
                l, r = l - 1, r + 1

            m = r - l - 1
            if m > longest[0]:
                longest[0] = m
                longest[1] = l + 1

        for i in range(n):
            # Check longest odd palindromic substring where s[i] is middle.
            find_palindromic(i, True)
            # Check longest even palindromic substring where s[i] and s[i+1] together are middle.
            find_palindromic(i, False)

        m, l = longest
        return s[l:l+m]

Extra

有个严格 O(n) 时间复杂度(O(n) 空间复杂度)的算法,叫 Manacher’s algorithm。

比较复杂,先不看了。

评论需要 JavaScript。