5.md

题目地址

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

解答1

def longestPalindrome(s):
    """ 最长回文子串中心扩展解法 """
    if not s:
        return ""
    start, end = 0, 0
    for i in range(len(s)):
        len1 = expandAroundCenter(s, i, i)
        len2 = expandAroundCenter(s, i, i + 1)
        len_ = len1 if len1 > len2 else len2

        if len_ > end - start:
            start = i - (len_ - 1) // 2
            end = i + len_ // 2

    return s[start:end + 1]

解答2

def expandAroundCenter(s, left, right):
    """ 最长回文子串的中心扩展算法 """
    L, R = left, right
    while L >= 0 and R < len(s) and s[L] == s[R]:
        L -= 1
        R += 1

    return R - L - 1

解答3

def manacher(s):
    """ 最长回文子串马拉车算法 """
    if s == '':
        return ''
    t = '^#' + '#'.join(s) + '#$'
    c = d = 0
    p = [0] * len(t)
    for i in range(1, len(t) - 1):
        mirror = 2 * c - i
        p[i] = max(0, min(d - i, p[mirror]))

        while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
            p[i] += 1
        if i + p[i] > d:
            c = i
            d = i + p[i]
    (k, i) = max((p[i], i) for i in range(1, len(t) - 1))
    return s[(i - k) // 2:(i + k) // 2]

解答4

def slidingWindow(s):
    """ 最长回文子串滑动窗口 """
    start, maxl = 0, 0
    for i in range(len(s)):
        if i - maxl >= 1 and s[i - maxl - 1:i + 1] == s[i - maxl - 1:i + 1][::-1]:
            start = i - maxl - 1
            maxl += 2
        if i - maxl >= 0 and s[i - maxl:i + 1] == s[i - maxl:i + 1][::-1]:
            start = i - maxl
            maxl += 1
    return s[start:start + maxl]