5. Longest Palindromic Substring
給定一個字符串 s，返回 s 中最長的回文子串。
Python
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) < 2:
return s
start, max_length = 0, 1
def expandAroundCenter(left: int, right: int):
nonlocal start, max_length
while left >= 0 and right < len(s) and s[left] == s[right]:
current_length = right - left + 1
if current_length > max_length:
start = left
max_length = current_length
left -= 1
right += 1
for i in range(len(s)):
expandAroundCenter(i, i) # odd length palindromes
expandAroundCenter(i, i + 1) # even length palindromes
return s[start:start + max_length]
16.44MB 328ms
C++
#include <string>
using namespace std;
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() < 2) {
return s;
}
int start = 0, maxLength = 1;
auto expandAroundCenter = [&](int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
int currentLength = right - left + 1;
if (currentLength > maxLength) {
start = left;
maxLength = currentLength;
}
left--;
right++;
}
};
for (int i = 0; i < s.size(); ++i) {
expandAroundCenter(i, i); // odd length palindromes
expandAroundCenter(i, i + 1); // even length palindromes
}
return s.substr(start, maxLength);
}
};
8.06MB, 12ms
Javascript
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
if (s.length < 2) {
return s;
}
let start = 0, maxLength = 1;
const expandAroundCenter = (left, right) => {
while (left >= 0 && right < s.length && s[left] === s[right]) {
let currentLength = right - left + 1;
if (currentLength > maxLength) {
start = left;
maxLength = currentLength;
}
left--;
right++;
}
};
for (let i = 0; i < s.length; i++) {
expandAroundCenter(i, i); // odd length palindromes
expandAroundCenter(i, i + 1); // even length palindromes
}
return s.substring(start, start + maxLength);
};
50.27MB, 76ms
