5. Longest Palindromic Substring
題目敘述
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 <= 1000
s
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
/**
* @param {string} s
* @return {string}
*/
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
/**
* @param {string} s
* @return {string}
*/
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