暴力解法O(n ^ 3)
// 暴力解法会超时,不推荐使用。
class Solution {
public:
// 检测 l 和 r 之间的字符串是否为回文串
bool func(string s, int l , int r)
{
while(l < r)
{
if(s[l] == s[r])
{
l++;
r--;
}
else
return false;
}
return true;
}
string longestPalindrome(string s) {
if(!s.size()) return "";
// 暴力枚举
int begin = 0;
int length = 0;
for(int i = 0; i < s.size(); ++i) // 枚举子串的起始位置
{
for(int j = 0; j < s.size(); ++j) // 枚举子串的终止位置
{
if(func(s, i, j))
{
if(j - i + 1 > length)
{
length = j - i + 1;
begin = i;
}
}
}
}
return s.substr(begin, length);
}
};
中心扩散法O(n ^ 2)
class Solution {
public:
// 寻找出从中心点扩散到周围的最长边界
pair<int, int> func(string s, int l, int r)
{
while(l >= 0 && r < s.size() && s[l] == s[r])
{
l--;
r++;
}
return {l + 1, r - 1};
}
string longestPalindrome(string s) {
// 边界条件
if(!s.size()) return "";
// 枚举字符串中的每一个中心点
int begin = 0, end = 0;
for(int i = 0; i < s.size(); ++i)
{
// 奇数扩散的方式
pair<int, int> p1 = func(s, i, i);
// 偶数扩散的方式
pair<int, int> p2 = func(s, i, i + 1);
// 找出最长的一个回文子串
if(p1.second - p1.first > end - begin)
{
begin = p1.first;
end = p1.second;
}
if(p2.second - p2.first > end - begin)
{
begin = p2.first;
end = p2.second;
}
}
return s.substr(begin, end - begin + 1);
}
};
动态规划O(n ^ 2)
// 动态规划
class Solution {
public:
string longestPalindrome(string s) {
// 空串时直接返回
if(!s.size()) return "";
// 记录状态
vector<vector<bool>> flag(s.size() + 1, vector<bool>(s.size() + 1, 0));
// 记录子串的位置及长度
int begin = 0, length = 0;
// 初始化状态(i ~ j区间只有一个字符时,此字符为回文串)
for(int i = 0; i < s.size(); ++i)
{
flag[i][i] = true;
if(flag[i][i])
{
begin = i;
length = 1;
}
}
// 初始化状态(i ~ j区间有两个字符时,如果两个字符相等则为回文串)
for(int i = 0; i + 1 < s.size(); ++i)
{
flag[i][i + 1] = s[i] == s[i + 1];
if(flag[i][i + 1])
{
begin = i;
length = 2;
}
}
// 状态转移(i ~ j区间有两个以上的字符时,进行状态转移)
for(int len = 3; len <= s.size(); ++len)
{
for(int i = 0; i + len - 1 < s.size(); ++i)
{
// 子串起始为 i, 终止为 i + len - 1
flag[i][i + len - 1] = flag[i + 1][i + len - 2] && s[i] == s[i + len - 1];
if(flag[i][i + len - 1] && len > length)
{
begin = i;
length = len;
}
}
}
return s.substr(begin, length);
}
};