由于基礎(chǔ)還不是很牢固 一時(shí)間只能想到暴力的解法:

取遍每個(gè)子串 總數(shù)量n+n-1+n-2+…+1 =O(n^2)
判斷每個(gè)子串是否屬于回文串 O(n)
故總時(shí)間復(fù)雜度為O(n^3)

class Solution {
public:string longestPalindrome(string s) {
int max=0;string ret;for(int i=0;i<s.size();i++)for(int j=1;j<=s.size()-i;j++){string s1=s.substr(i,j);if(Judeg(s1)>max){max=Judeg(s1);ret=s1;}}return ret;}int Judeg(string s)
{int i,j;for(i=0,j=s.size()-1;i<=j;i++,j--){if(s[i]!=s[j])return 0;}return s.size();
}
};

在查閱題解以后 比較簡單易懂的還是動態(tài)規(guī)劃算法
設(shè)某子串的左下標(biāo)為i 右下標(biāo)為j
則該子串是不是回文串可以走如下流程:
1.s[i]和s[j]不相等 那么一定不是回文子串 dp[i][j]=false
2.在s[i]和s[j]已經(jīng)相等的基礎(chǔ)上 若子串的長度<=3 那么一定是回文串 dp[i][j]=true
3.最后一種情況 dp[i][j]=dp[i+1][j-1]
一個(gè)很長的子串是不是回文串 取決于去掉首尾字符以后 中間的子串是不是回文串(動態(tài)規(guī)劃套娃)

時(shí)間復(fù)雜度為遍歷dp數(shù)組 故為O(n^2)
空間復(fù)雜度為開辟dp數(shù)組 故為O(n^2)

string longestPalindrome(string s) 
{int max=1,begin=0;int len=s.size();if(len<2)return s;bool **dp=new bool*[len];for(int i=0;i<len;i++){dp[i]=new bool [len];}for(int j=1;j<len;j++){for(int i=0;i<j;i++){if(s[i]!=s[j])dp[i][j]=false;else{if(j-i+1<=3)dp[i][j]=true;else{dp[i][j]=dp[i+1][j-1];}}if(dp[i][j]&&j-i+1>max){max=j-i+1;begin=i;}}}return s.substr(begin,max);
}