Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"Output: "bab"Note: "aba" is also a valid answer.
Example:
Input: "cbbd"Output: "bb"
題目理解：在串s中尋找回文串，輸出最長的任意一個回文子串
題目解法：
1：暴力搜索，二重循環[O(n2)]在0~s.length-1之間枚舉所有可能的子串，判斷其是否回文[O(n)]，所以該方案復雜度為【O(n3)】;
2：對稱搜索，按照回文對稱原則，0~s.length-1之間枚舉所有可能的子串對稱軸（aaaa:以a1為軸，maxlength=1，以a1與a2之間為軸，maxlength=2，以a2為軸，maxlength=3，以以a2與a3之間為軸，maxlength=4。再往后搜索就不會出現更大的回文子串了，因為剩余字符串的長度不足maxlength=4的一半，所以不用繼續掃描了。），根據對稱軸向兩邊同時擴展判斷是否回文。該方案復雜度為【O(n2)】,要注意的是注意區分以單個字母為軸和以一對字母為軸的情況;
3：動態規劃，有點類似于數學里歸納法的運用
（1）最基本的情況：單字符子串肯定回文（長度為1），相鄰相同字符肯定回文（長度為2）
（2）假設：從i開始，到j結尾的子串回文
（3）推導：若字符i-1==字符j+1 且 由i~j回文，那么i-1~j+1 回文。
該方法的需要一個二維矩陣來記錄較短的子串是否回文，所以空間復雜度躍至O（n2）,而時間復雜度因為二重循環的出現所以也是O（n2），具體的解釋見代碼注釋。
LeetCode提交結果：對稱搜索要遠優于動態規劃，很明顯動態規劃要遍歷所有長度的子串 和 所有起始位置（本例中無法做到剪枝），對稱搜索勝出。
上代碼（對稱搜索）：
public class Solution {	public String longestPalindrome(String s) {		char[] arrays=s.toCharArray();		int leftind=0,rightind=0;		int maxlen=0,maxloc=-1;		for(int i=0;i<(arrays.length-maxlen/2);i++){			//剩余字符串的長度不足maxlength=4的一半，所以不用繼續掃描了			/**			 * 首先是以單個字母為軸搜索			 * leftind,ightind分別為待搜索的對稱位置			 * 若二者都未越界，并且符合對稱則繼續向兩側擴展			 * 最后比較是否產生了新的最大回文子串			 */			leftind=i-1;			rightind=i+1;			while(leftind>-1 && rightind<arrays.length && arrays[leftind]==arrays[rightind]){				leftind-=1;				rightind+=1;			}			if(rightind-leftind-1 > maxlen){				maxlen=rightind-leftind-1;				maxloc=leftind+1;			}			/**			 * 以一對相同字母為對稱軸			 */			leftind=i;			rightind=i+1;			while(leftind>-1 && rightind<arrays.length && arrays[leftind]==arrays[rightind]){				leftind-=1;				rightind+=1;			}			if(rightind-leftind-1 > maxlen){				maxlen=rightind-leftind-1;				maxloc=leftind+1;			}		}		return String.valueOf(arrays,maxloc,maxlen);	}}動態規劃：
import java.util.Arrays;public class Solution {	public String longestPalindrome(String s) {		char[] arrays=s.toCharArray();		int length=s.length();		int maxlen=1,maxloc=0;	//最大回文子串的默認長度和位置		byte[][] flag=new byte[length][length];	//空間復雜度O(n2)的由來				/*for(byte[] e:flag){		 * 在使用Boolean類型矩陣時，若沒有此段操作，下方try中的代碼會報java.lang.NullPointerException異常，在使用基本類型byte時異常消失		 * 不過，使用基本類型真的會加快程序運行速度，簡單測試會提高50%左右。			Arrays.fill(e, (byte)0);		}*/		for(int i=0;i<length;i++){			//最小的回文子串長度為1，則將ii位置 置為TRUE			flag[i][i]=1;			if(i+1 < length && arrays[i]==arrays[i+1]){				//若遇到有相鄰相同字母時，maxlen改為2，位置修正				flag[i][i+1]=1;				maxlen=2;				maxloc=i;			}		}		for(int len=3;len<=length;len++){			for(int i=0;i<=length-len;i++){				//從長度為3的回文開始搜索，此時會用到長度為1的已記錄回文,即去掉長度為3的回文兩邊字符后，驗證長度為1的字符是否回文				try{					if(flag[i+1][i+len-2]==1 && arrays[i]==arrays[i+len-1]){					flag[i][i+len-1]=1;					maxlen=len;					maxloc=i;				}				}catch(Exception e){					System.out.PRintln((i)+" "+(i+len-1)+" "+len);				}			}		}		return s.substring(maxloc, maxloc+maxlen);		/**		 * 順便一提：i+=1比i++要快，s.substring 要比 String.valueof(arrays,bagin,length)要快		 */	}}