Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
给定一个字符串s，找到s中最长的回文子字符串。您可以假设s的最大长度为1000
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
回文的含义是：正着看和倒着看相同，如abba和yyxyy。
使用的是动态规划的方法，从边界值入手，即递归的逆过程，先求字符串最后两个字符是否为回文，一步步递推到整个字符串。
#include <iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int maxLen[10001][10001]; //字符串长度限制1000
class Solution {
public:
string longestPalindrome(string s) {
int i, j,start=0, maxNum = 1; //定义初始位置为0，最小长度为1；
int len = s.length();
string temp;
//初始化，将矩阵对角线初始化为1，一个字符是回文
for (i = 1; i <= len; i++)
{
for (j = 1; j <= len; j++)
{
maxLen[i][j] = 0;
}
maxLen[i][i] = 1;
}
//如果长度为1或者为空，返回
if (len == 1|| len == 0){
return s;
}
//遍历
for (i = len - 1; i > 0; i--)
{
for (j = i + 1; j <= len; j++)
{
if (s[i - 1] == s[j - 1]){//如果字符串为回文，两边相同，回文长度为中间字符串+2
maxLen[i][j] = maxLen[i + 1][j - 1] + 2;
if ((maxLen[i][j] > maxNum)&&maxLen[i][j]==j-i+1) //一个回文字符串的长度等于矩阵下标之差即字符串的下标之差加一
{
maxNum = maxLen[i][j];
start = i-1; //以一开头，所以减去1
}
}
}
}
//输出矩阵
for (i = 0; i <= len; i++)
{
for (j = 0; j <= len; j++)
{
cout << maxLen[i][j] << " ";
}
cout << endl;
}
//回文字符串长度为矩阵最大值
temp = s.substr(start, maxNum);
cout << "a: "<<start<<" maxnum: "<<maxNum<<" string: " << temp << endl;
return temp;
}
};
int main(){
Solution s;
string str;
while (cin >> str){
str = s.longestPalindrome(str);
cout << "str: " << str << endl;
}
}
【相关文档】
1.最长回文子串
