Longest Palindromic Substring-LeetCode

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)要快		 */	}}