前言：最近在忙专业实践和开题报告的事情，一直没时间刷题，另外第4个题卡了很久，现在也没解决，考虑了二分，然而我的方法边界条件太多，后续再说吧。
-------
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
首先想到的是一个差不多O(n^3)的方法，果然超时了。
public class Solution { public String longestPalindrome(String s) { int start = 0, end = 0; int maxLength = 0; for(int i = 0 ;i < s.length(); i ++){ for(int j = i + maxLength; j < s.length() && j <= 1000 ; j ++){ boolean isResult = true; int s_index =i, e_index = j; while(s_index <= e_index){ if(s.charAt(s_index)==s.charAt(e_index)){ s_index++; e_index--; }else{ isResult = false; break; } } if(isResult){ maxLength = j - i;start = i; end = j;} } } String result = s.substring(start,end); return result; } } 接下来进行了一些改进单还是O(n^3)的方法。
public class Solution { public String longestPalindrome(String s) { int start = 0, end = 0; int maxLength = 0; for(int i = 0 ;i < s.length(); i ++){ int j = ( i + 1000) >= s.length() ? s.length() - 1 : ( i + 1000); for(; j >= i + maxLength ; j --){ boolean isResult = true; int s_index =i, e_index = j; while(s_index <= e_index){ if(s.charAt(s_index)==s.charAt(e_index)){ s_index++; e_index--; }else{ isResult = false; break; } } if(isResult){ maxLength = j - i;start = i; end = j;} } } String result = s.substring(start,end); return result; } }接下来我思考，主要还是因为我自己是先框定一个范围，然后再判断回文串，干脆让他自己延伸。最坏情况应该是O(n^2),但是结果比我想象好。 Your runtime beats 79.38% of java submissions.
public class Solution { public int start = 0, end = 0, maxLength = 0; public String longestPalindrome(String s) { if(s.length() < 2){ return s; } for(int i = 0; i < s.length(); i++){ extendString(s,i,i); extendString(s,i,i+1); } return s.substring(start,end+1); } public void extendString(String s, int x, int y){ x = x - maxLength /2; y = y + maxLength /2; while( x >= 0 && y < s.length() && (y-x+1) <= 1000 && s.charAt(x) == s.charAt(y)){ x --; y ++; } if((y-x-1) > maxLength){ start = x + 1 ; end =y -1; maxLength = end - start + 1; } } } 总结，一开始想到的办法往往不是最好的，原因还是自己训练不够多，上述方法我还见到一个O(n)的方法，只能说太机智了，后续再补吧。
