125 - 5 最长回文子串

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd" 输出: "bb"

解答

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-bao-gu/

中心扩展

循环选择中心，然后两边扩展看看左右是否相等。

中心点不仅要选择字符，也要选择字符之间。

var longestPalindrome = function(s) {
  if (!s || s.length < 1) {
    return ""
  }
  let start = 0,
    end = 0
  for (let i = 0; i < s.length; i++) {
    const len1 = palindromic(s, i, i)
    const len2 = palindromic(s, i, i + 1)
    const max = Math.max(len1, len2)
    if (max > end - start) {
      start = i - ~~((max - 1) / 2)
      end = i + ~~(max / 2)
    }
  }
  return s.slice(start, end + 1)
};
const palindromic = function(s, left, right) {
  let L = left,
    R = right
  while (L >= 0 && R < s.length && s[L] === s[R]) {
    L--
    R++
  }
  return R - L - 1
}

Runtime: 80 ms, faster than 81.37% of JavaScript online submissions for Longest Palindromic Substring.

Memory Usage: 35.8 MB, less than 78.26% of JavaScript online submissions for Longest Palindromic Substring.

manacher

专门用于解决最长回文子串的问题

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/bu-chong-guan-fang-ti-jie-zuo-yi-dian-wei-xiao-de-/

• 先是在所有字符中间加一个#，这样字符中间也有格子。

检验最大字符串的时候，也没必要向后找，因为对称的关系，向前的距离就是原来数组中的最大长度。

image-20191028142902391

• 维护一个数组p，用来记录改字符的回文半径

• 其次维护 最大探索的右边max_right，和与之对应的探索中心mid

简言之，当 i < maxRight 的时候，p[i] 就是 p[mirror] 的信息（以mid为轴的mirror）

以 maxRight - i 作为参考标准，p[i] 的值应该是二者之中较小的那个值

就是说，i遍历到与mid对应的那个值，p[i]可以照抄p[mirror]，这样就省了再次计算的步骤了

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2:
            return s
        s_new = '#'+'#'.join(s)+'#'
        max_right = 0
        mid = 0
        l = len(s_new)
        p = [0]*l

        for i in range(l):
            if i < max_right:
                mirror = 2*mid-i
                p[i] = min(max_right-i, p[mirror])
            left = i-(1+p[i])
            right = i+(1+p[i])
            while left >= 0 and right < l and s_new[left] == s_new[right]:
                p[i] += 1
                left -= 1
                right += 1
            if i+p[i] > max_right:
                max_right = i+p[i]
                mid = i
        maxr = max(p)
        ans = p.index(maxr)
        maxr -= 1
        return s_new[ans-maxr:ans+maxr+1].replace('#', '')

Runtime: 80 ms, faster than 96.98% of Python3 online submissions for Longest Palindromic Substring.

Memory Usage: 13.8 MB, less than 22.69% of Python3 online submissions for Longest Palindromic Substring.

动态规划

回文串要满足，去掉最外侧两个字符，依然是回文串。或者去掉后根本不构成字符串。

https://leetcode.com/problems/longest-palindromic-substring/discuss/121496/Python-DP-solution

class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        if size < 2:
            return s
        dp = [[False for _ in range(size)] for _ in range(size)]
        longest = 1
        res = ""
        for i in range(size-1, -1, -1):
            for j in range(i, size):
                if s[j] == s[i] and (j-i <= 2 or dp[i+1][j-1]):
                    dp[i][j] = True
                    if res == "" or longest < j-i+1:
                        res = s[i:j+1]
                        longest = j-i+1
        return res

Runtime: 3376 ms, faster than 37.94% of Python3 online submissions for Longest Palindromic Substring.

Memory Usage: 22.4 MB, less than 5.04% of Python3 online submissions for Longest Palindromic Substring.