Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
思路一：动态规划(C++)
维护一个二维数组dp，其中dp[i][j]表示字符串区间[i, j]是否为回文串，当i = j时，只有一个字符，肯定是回文串，如果i = j + 1，说明是相邻字符，此时需要判断s[i]是否等于s[j]，如果i和j不相邻，即i - j >= 2时，除了判断s[i]和s[j]相等之外，dp[j + 1][i - 1]若为真，就是回文串
动态规划
class Solution {
public:
string longestPalindrome(const string& s) {
if (s.size() == 0) return "";
const int n = s.size();
bool f[n][n];
fill_n(&f[0][0], n*n, false);
size_t max_len = 1, start = 0;
for (size_t i = 0; i < s.size(); i++) {
f[i][i] = true;
for (size_t j = 0; j < i; j++) {
f[j][i] = (s[j] == s[i] && (i - j < 2 || f[j + 1][i - 1]));
if (f[j][i] && max_len < (i - j + 1)) {
max_len = i - j + 1;
start = j;
}
}
}
return s.substr(start, max_len);
}
};
时间复杂度o(n2),空间复杂度o(n2)
思路2：扩展中心(C++)
扩展中心
我们知道回文串一定是对称的，所以我们可以每次循环选择一个中心，进行左右扩展，判断左右字符是否相等即可。由于存在奇数的字符串和偶数的字符串，所以我们需要从一个字符开始扩展，或者从两个字符之间开始扩展，所以总共有 n + n - 1 个中心。
class Solution {
public:
std::string longestPalindrome(std::string s) {
if (s.size() < 2)
return s;
int len = s.size(), max_left = 0, max_len = 1, left, right;
for (int start = 0; start < len && len - start > max_len / 2;) {
left = right = start;
while (right < len - 1 && s[right + 1] == s[right])
++right;
start = right + 1;
while (right < len - 1 && left > 0 && s[right + 1] == s[left - 1]) {
++right;
--left;
}
if (max_len < right - left + 1) {
max_left = left;
max_len = right - left + 1;
}
}
return s.substr(max_left, max_len);
}
};
时间复杂度o(n^2),空间复杂度o(1)
思路3：Manacher’s Algorithm(C++)
class Solution {
public:
// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$".
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
string preProcess(const string& s) {
int n = s.length();
if (n == 0) return "^$";
string ret = "^";
for (int i = 0; i < n; i++) ret += "#" + s.substr(i, 1);
ret += "#$";
return ret;
}
string longestPalindrome(string s) {
string T = preProcess(s);
const int n = T.length();
// 以T[i]为中心，向左/右扩张的长度，不包含T[i]自己，
// 因此 P[i]是源字符串中回文串的长度
int P[n];
int C = 0, R = 0;
for (int i = 1; i < n - 1; i++) {
int i_mirror = 2 * C - i; // equals to i' = C - (i-C)
P[i] = (R > i) ? min(R - i, P[i_mirror]) : 0;
// Attempt to expand palindrome centered at i
while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
P[i]++;
// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome.
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// Find the maximum element in P.
int max_len = 0;
int center_index = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] > max_len) {
max_len = P[i];
center_index = i;
}
}
return s.substr((center_index - 1 - max_len) / 2, max_len);
}
};
时间复杂度o(n)，空间复杂度o(n)