題目敘述
Given a string s, return the longest palindromic substring in s.
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 <= 1000s consist of only digits and English letters.
Hint 1:
How can we reuse a previously computed palindrome to compute a larger palindrome?
Hint 2:
If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?
Hint 3:
Complexity based hint:
If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation?
題目翻譯
提供一個字串 s，從中找出最長的回文子字串。有沒有可能利用先前的條件，讓時間複雜度變成 O(n) 呢？
解法解析
這題如果不考慮將時間複雜度降到 O(n) 的話難度的確只有 Medium 吧，但是一但考量到複雜度整個就是 Hard 等級了，因為就會需要使用到所謂的馬拉車算法 (Manacher's Algorithm)。如果不考慮的話，大多就會使用了中心擴展法來解個題目。
解法範例
Go
Expand Around Center
func longestPalindrome(s string) string {
if len(s) < 2 {
return s
}
start, end := 0, 0
for i := 0; i < len(s); i++ {
len1 := expandAroundCounter(s, i, i)
len2 := expandAroundCounter(s, i, i+1)
var length int = len2
if len1 > len2 {
length = len1
}
if length > end-start {
start = i - (length-1)/2
end = i + length/2
}
}
return s[start : end+1]
}
func expandAroundCounter(s string, left int, right int) int {
for left >= 0 && right < len(s) && s[left] == s[right] {
left--
right++
}
return right - left - 1
}
Manacher's Algorithm
func longestPalindrome(s string) string {
var expandStr string = "#"
for _, c := range s {
expandStr += string(c) + "#"
}
var maxLen int = len(expandStr)
var P []int = make([]int, maxLen)
var center int = 0
var right int = 0
for i := 0; i < maxLen; i++ {
var mirror int = 2*center - i
if mirror < 0 {
mirror = 0
}
if right > i {
P[i] = P[mirror]
if P[mirror] > right-i {
P[i] = right - i
}
}
for i-P[i] >= 0 && i+P[i] < maxLen && expandStr[i-P[i]] == expandStr[i+P[i]] {
P[i]++
}
if i+P[i] > right {
center = i
right = i + P[i]
}
}
var maxIndex int = 0
for i, v := range P {
if v > P[maxIndex] {
maxIndex = i
}
}
var start int = (maxIndex - P[maxIndex] + 1) / 2
return s[start : start+P[maxIndex]-1]
}
JavaScript
Expand Around Center
var longestPalindrome = function (s) {
if (s.length === 0) return '';
else if (s === s.split('').reverse().join('')) return s;
let start = 0,
end = 0;
for (let i = 0; i < s.length; i++) {
const len1 = expandAroundCenter(s, i, i);
const len2 = expandAroundCenter(s, i, i + 1);
const length = Math.max(len1, len2);
if (length > end - start) {
start = i - Math.floor((length - 1) / 2);
end = i + Math.floor(length / 2);
}
}
return s.slice(start, end + 1);
};
const expandAroundCenter = (s, left, right) => {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return right - left - 1;
};
Manacher's Algorithm
var longestPalindrome = function (s) {
if (!s || !s.length) return '';
const str = `#${s.split('').join('#')}#`;
const n = str.length;
let center = 0,
radius = 0;
const P = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
if (i > radius) {
P[i] = 1;
} else {
const i_mirror = 2 * center - i > 0 ? 2 * center - i : 0;
P[i] = Math.min(P[i_mirror], radius - i);
}
let lo = i - P[i],
hi = i + P[i];
while (lo >= 0 && hi < n && str[lo] === str[hi]) {
lo--, hi++;
}
P[i] = hi - i;
if (i + P[i] > radius) {
center = i;
radius = i + P[i];
}
}
const maxLen = Math.max(...P);
const centerIndex = P.indexOf(maxLen);
const res = str.substring(centerIndex - maxLen + 1, centerIndex + maxLen);
return res.split('#').join('');
};
Kotlin
PHP
Python
Expand Around Center
class Solution:
def longestPalindrome(self, s: str) -> str:
if s == s[::-1]:
return s
start = end = 0
for i in range(len(s)):
len1 = self.expandAroundCenter(s, i, i)
len2 = self.expandAroundCenter(s, i, i + 1)
length = max(len1, len2)
if length > end - start:
start = i - (length - 1) // 2
end = i + length // 2
return s[start:end + 1]
def expandAroundCenter(self, s: str, left: int, right: int) -> int:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
Manacher's Algorithm
class Solution:
def longestPalindrome(self, s: str) -> str:
T = '#'.join('^{}$'.format(s))
n = len(T)
P = [0] * n
C = R = 0
for i in range(1, n - 1):
P[i] = (R > i) and min(R - i, P[2 * C - i])
while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
P[i] += 1
if i + P[i] > R:
C, R = i, i + P[i]
max_len, center_idex = max((n, i) for i, n in enumerate(P))
return s[(center_idex - max_len) // 2: (center_idex + max_len) // 2]
Rust
Swift
Reference