Type：medium
Given a string?s, find the longest palindromic substring in?s. You may assume that the maximum length of?s?is 1000.
Example 1:
Input:"babad"Output:"bab"Note:"aba" is also a valid answer.
Example 2:
Input:"cbbd"Output:"bb"
這道題有很多更簡(jiǎn)便的解法寸宏，但我想練一練動(dòng)態(tài)規(guī)劃颗品，因此用了動(dòng)態(tài)規(guī)劃去做。
本題題意為輸入一個(gè)字符串蛉抓，讓你找里面最長(zhǎng)的回文子字符串撑碴∫瓴眩基本想法是建立一個(gè)倒過(guò)來(lái)的string ss，兩者取最長(zhǎng)公共子字符串凌停。
若使用動(dòng)態(tài)規(guī)劃粱年，則建立一個(gè)temp[][]布爾型數(shù)組，temp[i][j]用來(lái)記錄s[i]到s[j]之間的子字符串是否為回文罚拟。
首先給單個(gè)字符以及長(zhǎng)度為2的字符串賦初始值台诗。單個(gè)字符容易，用i值遍歷s舟舒，從0到s.length()的temp[i][i]都賦為true拉庶；雙字符同理，若temp[i] == temp[i+1]秃励，則賦為true氏仗。
接下來(lái)應(yīng)用到整個(gè)字符串，對(duì)于長(zhǎng)度為3及以上的字符串，首先匹配頭尾字符s[i]皆尔、s[j]是否相同呐舔，若不同直接賦為false，若相同則判斷temp[s[i+1]][s[j-1]]是否為真慷蠕，若為真則該字符串為回文珊拼，若為假則該字符串不是回文，返回false流炕。在遍歷的過(guò)程中記錄最長(zhǎng)的回文字符串即可澎现。
此題有兩個(gè)坑：
一是在class中的變量并不是全局變量，temp[][]沒(méi)有初始的false值每辟，因此在每一步判斷中都要給temp賦值剑辫。
二是temp數(shù)組開(kāi)的大小，我最開(kāi)始賦temp[n][n]會(huì)報(bào)錯(cuò)渠欺，因此要開(kāi)得足夠大妹蔽。
附代碼：
class Solution {
public:
? ? string longestPalindrome(string s) {
? ? ? ? int n = s.length();
? ? ? ? if(n<2) return s;
? ? ? ? bool temp[2000][2000];
? ? ? ? int maxLen = 1;
? ? ? ? int start = 0;
? ? ? ? int end = 0;
? ? ? ? for(int i=0; i<n; i++){
? ? ? ? ? ? temp[i][i] = true;
? ? ? ? }
? ? ? ? for(int i=0; i<n-1; i++){
? ? ? ? ? ? if(s[i] == s[i+1]){
? ? ? ? ? ? ? ? temp[i][i+1] = true;
? ? ? ? ? ? ? ? maxLen = 2;
? ? ? ? ? ? ? ? start = i;
? ? ? ? ? ? ? ? end = i+1;
? ? ? ? ? ? }
? ? ? ? ? ? else temp[i][i+1] = false;
? ? ? ? }
? ? ? ? for(int len=3; len<=n; len++){
? ? ? ? ? ? for(int i=0; i<=n-len; i++){
? ? ? ? ? ? ? ? if(s[i] != s[i+len-1]) temp[i][i+len-1] = false;
? ? ? ? ? ? ? ? else if(!temp[i+1][i+len-2]) temp[i][i+len-1] = false;
? ? ? ? ? ? ? ? else if(temp[i+1][i+len-2]){
? ? ? ? ? ? ? ? ? ? temp[i][i+len-1] = true;
? ? ? ? ? ? ? ? ? ? if(len>=maxLen){
? ? ? ? ? ? ? ? ? ? ? ? start = i;
? ? ? ? ? ? ? ? ? ? ? ? end = i+len-1;
? ? ? ? ? ? ? ? ? ? ? ? maxLen = len;? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return s.substr(start, maxLen);
? ? }
};
