题目描述：
解法一（暴力求解）：
class Solution {
public:
string longestPalindrome(string s) {
int n=s.size();
string res;
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
string temp=s.substr(i,j-i+1),rev=temp;
reverse(rev.begin(),rev.end());
if(temp==rev&&temp.size()>res.size())
res=temp;
}
}
return res;
}
};
class Solution {
public:
string longestPalindrome(string s) {
string res;
string str;
for(int i=0;i<s.size();i++){
for(int j=i;j<s.size();j++){
str+=s[j];
string rev=str;
reverse(rev.begin(),rev.end());
if(str==rev&&str.size()>res.size())
res=str;
}
str="";
}
return res;
}
};
class Solution {
public:
bool isPalindrome(string s){
int len=s.size();
for(int i=0;i<len/2;i++){
if(s[i]!=s[len-i-1])
return false;
}
return true;
}
string longestPalindrome(string s) {
int n=s.size();
string res;
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
string temp=s.substr(i,j-i+1);
if(isPalindrome(temp)&&temp.size()>res.size())
res=temp;
}
}
return res;
}
};超时了！
解法二（最长公共子串）：
class Solution {
public:
bool isPalindrome(string s) {
int len = s.size();
for (int i = 0; i<len; i++) {
if (s[i] != s[len - i - 1])
return false;
}
return true;
}
string longestPalindrome(string s) {
string res;
string rev = s;
reverse(rev.begin(), rev.end());
if(s==rev) return s;
for (int i = 0; i<s.size(); i++) {
for (int j = i; j<s.size(); j++) {
string temp = s.substr(i, j - i + 1);
if(res.size()>=temp.size()) continue;
else if (rev.find(temp)!=string::npos ){
if(isPalindrome(temp)) {
res = temp;
}
}
else break;
}
}
return res;
}
};
class Solution {
public:
string longestPalindrome(string s) {
string res;
string rev = s;
reverse(rev.begin(), rev.end());
if(rev==s) return s;
string temp;
for (int i = 0; i<s.size(); i++) {
for (int j = i; j<s.size(); j++) {
temp += s[j];
if (res.size()>=temp.size())
continue;
else if(rev.find(temp)!=string::npos){
string q=temp;
std::reverse(q.begin(),q.end());
if(q==temp)
res=temp;
}
else break;
}
temp="";
}
return res;
}
};
这种方法已经通过了。
解法三（动态规划）：
class Solution {
public:
string longestPalindrome(string s) {
int len=s.length();
if(len<2) return s;
bool dp[len][len];
memset(dp,0,sizeof(dp));
string res;
res+=s[0]; //最少一个字符
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;
res=s.substr(i,2); //两个字符回文情况
}
}
for(int l=3;l<=len;l++){
for(int i=0;i<=len-l;i++){
int j=i+l-1;
if(s[i]==s[j]&&dp[i+1][j-1]){
dp[i][j]=1;
if(j-i+1>res.size())
res=s.substr(i,j-i+1);
}
}
}
return res;
}
};
class Solution {
public:
string longestPalindrome(string s) {
int n=s.length();
if(n<2) return s;
vector<vector<bool>> dp(n,vector<bool>(n,0));
int start=0,len=1;
for(int i=0;i<n;i++){
dp[i][i]=1;
if(i<n-1&&s[i]==s[i+1]){
dp[i][i+1]=1;
start=i;len=2;
}
}
for(int l=3;l<=n;l++){
for(int i=0;i+l-1<n;i++){
int j=i+l-1;
if(s[i]==s[j]&&dp[i+1][j-1]){
dp[i][j]=1;
start=i;
len=l;
}
}
}
return s.substr(start,len);
}
};
class Solution {
public:
string longestPalindrome(string s) {
int n=s.size();
string res;
vector<vector<bool>> dp(n,vector<bool>(n,0));
for(int i=0;i<n;i++){ //开始位置
for(int j=i;j>=0;j--){ //中止位置
if(s[i]==s[j]&&(i-j<2||dp[j+1][i-1]==1)){
dp[j][i]=1;
if(i-j+1>res.size()) res=s.substr(j,i-j+1);
}
}
}
return res;
}
};解法四（中心扩展）：
class Solution {
public:
int Expand(string& s, int ll, int rr) {
if (s[ll] != s[rr]) return 1;
while (s[ll] == s[rr]) {
if (ll == 0 || rr == s.size() - 1)
break;
else {
ll--;
rr++;
}
}
return s[ll] == s[rr]? rr - ll + 1: rr - ll-1;
}
string longestPalindrome(string s) {
int n = s.size();
if (n<2) return s;
int start = 0, len = 1;
for (int i = 0; i<n - 1; i++) {
int lenth1 = Expand(s, i, i);
int lenth2 = Expand(s, i, i + 1);
int temp = max(lenth1, lenth2);
if (len<temp) {
start = i - (temp - 1) / 2;
len = temp;
}
}
return s.substr(start, len);
}
};解法五（Manacher 算法，马拉车算法）：
这是一个专门用作处理最长回文子串的方法，思想很巧妙，比较难以理解，这里直接借用了别人的讲解方法。其实主要思想是，把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串，这个叫中心扩展法，但是这个方法还要考虑到处理 abba 这种偶数个字符的回文串。Manacher 法将所有的字符串全部变成奇数个字符。
有时间研究一下！
题目描述：
解法一（暴力解法）：
class Solution {
public:
string shortestPalindrome(string s) {
int n=s.size();
if(n<2) return s;
int len=1;
string res;
string temp;
for(int i=0;i<n;i++){
temp+=s[i];
string rev=temp;
reverse(rev.begin(),rev.end());
if(rev==temp)
len=temp.size();
}
res=s.substr(len,n-len);
reverse(res.begin(),res.end());
return res+s;
}
};
class Solution {
public:
string shortestPalindrome(string s) {
int n=s.size();
string rev=s;
reverse(rev.begin(),rev.end());
for(int i=0;i<n;i++){
if(s.substr(0,n-i)==rev.substr(i))
return rev.substr(0,i)+s;
}
return "";
}
};超时了！
解法二（双指针减少搜索长度）：
class Solution {
public:
string shortestPalindrome(string s) {
int n=s.size();
int i=0;
for(int j=n-1;j>=0;j--){
if(s[j]==s[i])
i++;
}
if(i==n)
return s;
string revlast=s.substr(i);
reverse(revlast.begin(),revlast.end());
return revlast+shortestPalindrome(s.substr(0,i))+s.substr(i);
}
};解法三（KMP算法）：
KMP算法是一个时间复杂度为 O(n+m) 的字符串匹配算法，其中 n 和 m 分别是待匹配文本和字符串的长度。KMP算法的核心是部分匹配表（查找表）f(s)。
有时间研究一下
题目描述：
解法：
四种情况：
- 数组里有空字符串，并且数组里还有自己就是回文的字符串，每出现一个可与空字符串组成两对。（可并入3，4）
- 如果自己的翻转后的字符串也在数组里，可以组成一对，注意翻转后不能是自己。
- 如果某个字符串能找到一个分割点，分割点前的部分是回文，后半部分翻转后也在数组里，可组成一对。
- 把3反过来，如果后部分是回文，前半部分翻转后在数组里，可组成一对。
class Solution {
public:
bool isPalindrome(string& s,int i,int j){
while(i<j){
if(s[i]!=s[j])
return false;
i++;j--;
}
return true;
}
vector<vector<int>> palindromePairs(vector<string>& words) {
int n=words.size();
unordered_map<string,int> mp; //先把每个字符串对应的位置对应起来
set<int> lens; //用来搜索可以匹配够成回文的串
vector<vector<int>> res;
for(int i=0;i<n;i++){
mp[words[i]]=i;
lens.insert(words[i].size());
}
for(int i=0;i<n;i++){
int len=words[i].size();
string rev=words[i];
reverse(rev.begin(),rev.end());
if(mp.count(rev)&&mp[rev]!=i) //整个串与其他串构成回文，对应方式2
res.push_back(vector<int>{i,mp[rev]});
auto pos=lens.find(len);
for(auto it=lens.begin();it!=pos;it++){ //串的前段或者后端的一部分与其他串构成回文，其他串长度必然小于当前串
if(isPalindrome(words[i],0,len-*it-1)&&mp.count(rev.substr(0,*it))){ //两种构成回文的方式 对应方式3
res.push_back(vector<int>{mp[rev.substr(0,*it)],i});
}
if(isPalindrome(words[i],*it,len-1)&&mp.count(rev.substr(len-*it,*it))){ //对应方式4
res.push_back(vector<int>{i,mp[rev.substr(len-*it)]});
}
}
}
return res;
}
};题目描述：
解法一（回溯）：
class Solution {
public:
bool isPalindrome(string& s, int l, int r) { //判断[l,r]之间是否位回文
while (l<r) {
if (s[l++] != s[r--])
return false;
}
return true;
}
void helper(vector<vector<string>>& res, string& s, int ll, int rr, vector<string>& temp) {
if (ll == rr) res.push_back(temp);
for (int len = 1; len <= rr - ll; len++) { //以长度为标尺，长度扩大
if (isPalindrome(s, ll, ll + len - 1)) {
temp.push_back(s.substr(ll, len));
helper(res, s, ll + len, rr, temp);
temp.erase(temp.end() - 1);
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> temp;
helper(res, s, 0, s.size(), temp);
return res;
}
};解法二（dfs+回溯）：
class Solution {
public:
void DFS(string& s, vector<vector<string>>& res, vector<string>& temp, vector<vector<bool>>& dp, int index) {
if (index == s.size()) {
res.push_back(temp);
}
for (int i = index; i<s.size(); i++) {
if (dp[index][i]) {
temp.push_back(s.substr(index, i - index + 1));
DFS(s, res, temp, dp, i + 1);
temp.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, 0));
for (int i = 0; i<n; i++) {
for (int j = i; j >= 0; j--) {
if (s[i] == s[j] && (i - j<2 || dp[j + 1][i - 1]))
dp[j][i] = 1;
}
}
vector<vector<string>> res;
vector<string> temp;
DFS(s, res, temp, dp, 0);
return res;
}
};
class Solution {
public:
bool dp[1001][1001] = { 0 };
vector<vector<string>> res;
vector<string> tmp;
vector<vector<string>> partition(string s) {
int l = s.length();
//两个for循环构造回文串的dp数组
for (int i = 0; i < l; i++) {
for (int j = 0; j <= i; j++) {
if (s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1]))
dp[j][i] = 1;
}
}
dfs(0, l, s);
return res;
}
void dfs(int i,int n,string s) {
if (i == n) res.push_back(tmp);
for (int j = i; j < n; j++) {
if (dp[i][j]) {
tmp.push_back(s.substr(i, j-i+1));
dfs(j + 1, n, s);
tmp.erase(tmp.end() - 1);
}
}
}
};题目描述：
解法：
class Solution {
public:
int minCut(string s) {
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n,0));
vector<int> res(n+1,INT_MAX);
res[0]=-1;
for(int i=0;i<n;i++){
for(int j=i;j>=0;j--){
if(s[i]==s[j]&&(i-j<2||dp[j+1][i-1])){
dp[j][i]=1;
res[i+1]=min(res[i+1],1+res[j]);
}
}
}
return res[n];
}
};
class Solution {
public:
int minCut(string s) {
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n,0));
vector<int> res(n,INT_MAX);
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
if(s[i]==s[j]&&(i-j<2||dp[j+1][i-1])){
dp[j][i]=1;
if(j==0) res[i]=0;
else res[i]=min(res[i],1+res[j-1]);
}
}
}
return res[n-1];
}
};