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
专门用于解决最长回文子串的问题
先是在所有字符中间加一个#，这样字符中间也有格子。
检验最大字符串的时候，也没必要向后找，因为对称的关系，向前的距离就是原来数组中的最大长度。
维护一个数组p，用来记录改字符的回文半径
其次维护 最大探索的右边max_right，和与之对应的探索中心mid
简言之，当 i < maxRight 的时候，p[i] 就是 p[mirror] 的信息（以mid为轴的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.
动态规划
回文串要满足，去掉最外侧两个字符，依然是回文串。或者去掉后根本不构成字符串。
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.
