算法
时间复杂度: O(n^2)
总空间复杂度: O(n)
额外空间复杂度: O(1)
C++代码
class Solution {
public:
static string longestPalindrome(const string &str) {
if (str.size() <= 1) {
return str;
}
const int n = static_cast<int>(str.size());
int begin = 0;
int size = 1;
for (int i = 1; i < n; ++i) {
const int size1 = palindromeSize(str, i - 1, i + 1);
const int size0 = palindromeSize(str, i - 1, i);
const int sizeMax = max(size1, size0);
if (size < sizeMax) {
begin = i - (sizeMax >> 1);
size = sizeMax;
}
}
return str.substr(begin, size);
}
private:
static int palindromeSize(const string &str, int left, int right) {
const int n = static_cast<int>(str.size());
for (; left >= 0 && right < n && str[left] == str[right]; --left, ++right) {
}
return right - left - 1;
}
};
Java代码
class Solution {
public static String longestPalindrome(String str) {
if (str.length() <= 1) {
return str;
}
int begin = 0;
int size = 1;
for (int i = 1; i < str.length(); ++i) {
final int size1 = palindromeSize(str, i - 1, i + 1);
final int size0 = palindromeSize(str, i - 1, i);
final int sizeMax = Math.max(size1, size0);
if (size < sizeMax) {
begin = i - (sizeMax >> 1);
size = sizeMax;
}
}
return str.substring(begin, begin + size);
}
private static int palindromeSize(String str, int left, int right) {
for (; left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right); --left, ++right) {
}
return right - left - 1;
}
}
Python3代码
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) <= 1:
return s
begin = 0
size = 1
for i in range(1, len(s)):
size1 = self.__palindromeSize(s, i - 1, i + 1)
size0 = self.__palindromeSize(s, i - 1, i)
sizeMax = max(size1, size0)
if size < sizeMax:
begin = i - (sizeMax >> 1)
size = sizeMax
return s[begin:begin + size]
def __palindromeSize(self, s, left, right) -> int:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1