5. 最長(zhǎng)回文子串
給定一個(gè)字符串 s羞海，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba"也是一個(gè)有效答案判沟。
示例 2：
輸入: "cbbd"
輸出: "bb"
思路：常規(guī)暴力法：求所有子串，逐個(gè)驗(yàn)證是否是回文子串利赋，n的平方*n水评，時(shí)間復(fù)雜度O(n3);
動(dòng)態(tài)規(guī)劃：動(dòng)態(tài)規(guī)劃是一個(gè)不錯(cuò)的思路，首先媚送，一個(gè)首尾索引分別為i和j的字符串是不是回文中燥，只需要比對(duì)i和j是否相等，并且i+1到j(luò)-1的字符串是否為回文子串塘偎。這樣我們記憶dp[i][j]是否為回文字符串的所有結(jié)果疗涉。如果是一個(gè)字符肯定是回文子串，如果是兩個(gè)字符吟秩，相等就是回文子串咱扣。由于保存了dp[i][j]的結(jié)果，時(shí)間復(fù)雜度O(n2),空間復(fù)雜度O(n2)
class Solution {
public:
string longestPalindrome(string s) {
//字符串長(zhǎng)度
int size=s.size();
bool dp[size][size];
// fill_n(&dp[size][size],size*size,false);
int max_len=1; //保存最長(zhǎng)回文子串長(zhǎng)度
int start=0; //保存最長(zhǎng)回文子串起點(diǎn)
//i是右標(biāo)涵防，開始遍歷i
for(int i=0;i<size;++i)
{
//j是左標(biāo)
for(int j=0;j<=i;++j)
{
if(i-j<2){
//兩個(gè)字符的時(shí)候闹伪，直接比對(duì)值 一個(gè)字符就是true
dp[j][i]=(s[i]==s[j]);
}
else{
//動(dòng)態(tài)規(guī)劃思路，j+1的和i-1一定是已經(jīng)填充過得值壮池，因?yàn)閕是從左往右遍歷的
dp[j][i]=(s[i]==s[j] && dp[j+1][i-1]);
}
if(dp[j][i] && max_len<(i-j+1))
{
max_len=i-j+1;
start=j;
}
}
}
return s.substr(start,max_len);
}
};
小思考：空間復(fù)雜度還是可以優(yōu)化的偏瓤，因?yàn)橹恍枰敵鲎畲蠡匚淖哟梢灾槐４嫔弦惠喌慕Y(jié)果值椰憋。不保存全部厅克。
6. Z字形變換
將字符串 "PAYPALISHIRING" 以Z字形排列成給定的行數(shù)：
P A H N
A P L S I I G
Y I R
之后從左往右，逐行讀取字符："PAHNAPLSIIGYIR"
實(shí)現(xiàn)一個(gè)將字符串進(jìn)行指定行數(shù)變換的函數(shù):
string convert(string s, int numRows);
示例 1:
輸入: s = "PAYPALISHIRING", numRows = 3
輸出: "PAHNAPLSIIGYIR"
示例 2:
輸入: s = "PAYPALISHIRING", numRows = 4
輸出: "PINALSIGYAHRPI"
解釋:
P I N
A L S I G
Y A H R
P I
這是一道常規(guī)找規(guī)律的題目橙依，我們按行遍歷即可证舟，時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(n)
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
string ret;
int n = s.size();
int cycleLen = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycleLen) {
ret += s[j + i];
//不是第一行也不是最后一行硕旗，中間的字符
if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
ret += s[j + cycleLen - i];
}
}
return ret;
}
};
