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, and there exists one unique longest palindromic substring.
分析
最长回文子串,非常经典的题。
思路一:暴力枚举,以每个元素为中间元素,同时从左右出发,复杂度O(n^2)
。
思路二:记忆化搜索,复杂度O(n^2)
。设f[i][j]
表示[i,j]之间的最长回文子串,递推方程如下:
f[i][j] = if (i == j) S[i]
if (S[i] == S[j] && f[i+1][j-1] == S[i+1][j-1]) S[i][j]
else max(f[i+1][j-1], f[i][j-1], f[i+1][j])
思路三:动规,复杂度O(n^2)
。设状态为f(i,j)
,表示区间[i,j]是否为回文串,则状态转移方程为
思路四:Manacher’s Algorithm, 复杂度O(n)
。详细解释见 http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html。
备忘录法
// Longest Palindromic Substring
// 备忘录法,会超时
// 时间复杂度O(n^2),空间复杂度O(n^2)
namespace std {
template<>
struct hash<pair<int, int>> {
size_t operator()(pair<int, int> const& p) const {
return p.first * 31 + p.second;
}
};
}
class Solution {
public:
string longestPalindrome(string const& s) {
cache.clear();
return cachedLongestPalindrome(s, 0, s.length() - 1);
}
private:
unordered_map<pair<int, int>, string> cache;
string longestPalindrome(string const& s, int i, int j) {
const int length = j - i + 1;
if (length < 2) return s.substr(i, length);
const string& s1 = cachedLongestPalindrome(s, i + 1, j - 1);
if (s1.length() == length - 2 && s[i + 1] == s[j - 1])
return s.substr(i, length);
const string& s2 = cachedLongestPalindrome(s, i + 1, j);
const string& s3 = cachedLongestPalindrome(s, i, j - 1);
// return max(s1, s2, s3)
if (s1.length() > s2.length()) return s1.length() > s3.length() ? s1 : s3;
else return s2.length() > s3.length() ? s2 : s3;
}
string cachedLongestPalindrome(string const& s, int i, int j) {
auto key = make_pair(i, j);
auto pos = cache.find(key);
if (pos != cache.end()) return pos->second;
else return cache[key] = longestPalindrome(s, i, j);
}
};
动规
// Longest Palindromic Substring
// 动规,时间复杂度O(n^2),空间复杂度O(n^2)
class Solution {
public:
string longestPalindrome(const string& s) {
const int n = s.size();
bool f[n][n];
fill_n(&f[0][0], n * n, false);
// 用 vector 会超时
//vector > f(n, vector(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++) { // [j, i]
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);
}
};
Manacher’s Algorithm
// Longest Palindromic Substring
// Manacher’s Algorithm
// 时间复杂度O(n),空间复杂度O(n)
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);
}
};