1、直接法
class Solution {
public:
string longestPalindrome(string s) {
if (s.length() == 1) return s;//大小为1的字符串必为回文串
string rev = s;//rev存放s反转结果
string res;//存放结果
std::reverse(rev.begin(), rev.end());
if (rev == s) return s;
int len = 0;//存放回文子串的长度
for (int i = 0; i<s.length(); i++)//查找s与rev的最长公共子串
{
string temp;//存放待验证子串
for (int j = i; j<s.length(); j++)
{
temp = temp + s[j];
if (len >= temp.length())
continue;
else if (rev.find(temp) != -1)//在rev中找到temp
{
string q = temp;//q用来验证temp是否是回文子串
std::reverse(q.begin(), q.end());
if (q == temp)
{
len = temp.length();
res = temp;
}
}
else break;
}
temp = "";
}
return res;
}
};注：也是简单的遍历方法，通过下面进行寻找是否有当前遍历到的子字符串是否被包含在反向串内，能够节约时间。
else if (rev.find(temp) != -1)//在rev中找到temp
{
string q = temp;//q用来验证temp是否是回文子串
std::reverse(q.begin(), q.end());
if (q == temp)
{
len = temp.length();
res = temp;
}
}2、动态规划法
class Solution {
public:
string longestPalindrome(string s) {
int len = s.size();
if (len == 0 || len == 1)
return s;
int start = 0;//回文串起始位置
int max = 1;//回文串最大长度
vector<vector<int>> dp(len, vector<int>(len));//定义二维动态数组
for (int i = 0; i<len; i++)//初始化状态
{
dp[i][i] = 1;
if (i<len - 1 && s[i] == s[i + 1])
{
dp[i][i + 1] = 1;
max = 2;
start = i;
}
}
for (int l = 3; l <= len; l++)//l表示检索的子串长度，等于3表示先检索长度为3的子串
{
for (int i = 0; i + l - 1<len; i++)
{
int j = l + i - 1;//终止字符位置
if (s[i] == s[j] && dp[i + 1][j - 1] == 1)//状态转移
{
dp[i][j] = 1;
start = i;
max = l;
}
}
}
print_myvector(dp);
return s.substr(start, max);//获取最长回文子串
}
void print_myvector(vector<vector<int>> v_ij)
{
for (size_t i = 0; i < v_ij.size(); i++)
{
for (size_t j = 0; j < v_ij[0].size(); j++)
{
cout << v_ij[i][j] << " ";
}
cout << endl;
}
}
};注：这其中的重点就在于，通过一个数组来存放子串。通过动态数组将回文子串存储下来，可以节约查询小一级子串是否为回文子串，我还用的例子：
abcdavdcarrggabcdefghijklmnaanmlkjihgfedcba
将dp打印出来，滚动鼠标就会看到其中的特征：
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13、中心扩展法
注：其实每个回文子串都是有一个对称中心的，通过对中心的扩展，来寻找最大回文子串，效率还蛮高的
class Solution {
public:
string longestPalindrome(string s) {
int len = s.size();
if (len == 0 || len == 1)
return s;
int start = 0;//记录回文子串起始位置
int end = 0;//记录回文子串终止位置
int mlen = 0;//记录最大回文子串的长度
for (int i = 0; i<len; i++)
{
int len1 = expendaroundcenter(s, i, i);//一个元素为中心
int len2 = expendaroundcenter(s, i, i + 1);//两个元素为中心
mlen = max(max(len1, len2), mlen);
if (mlen>end - start + 1)
{
start = i - (mlen - 1) / 2;
end = i + mlen / 2;
}
}
return s.substr(start, mlen);
//该函数的意思是获取从start开始长度为mlen长度的字符串
}
private:
int expendaroundcenter(string s, int left, int right)
//计算以left和right为中心的回文串长度
{
int L = left;
int R = right;
while (L >= 0 && R<s.length() && s[R] == s[L])
{
L--;
R++;
}
return R - L - 1;
}
};方便大家测试 main函数：
int main(int argc, char *argv[])
{
string str("abcdavdcarrggabcdefghijklmnaanmlkjihgfedcba");
Solution my_solu;
string str_out = my_solu.longestPalindrome(str);
return 0;
}
版权声明：本文为weixin_42208807原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。