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"
題目分析：返回一個字符串的最長回文子串。首先明確一下回文串的概念。一個回文串也就是一個字符串毯炮，它從正著讀和反著讀都是一樣的份殿。例如"aba"就是一個回文串，"abba"也是回文串枝秤，而"abc"則不是醋拧。
本題最簡單的想法就是設(shè)置兩個指針i，j淀弹，然后依次判斷i,j位置之中的字符串是否為回文串丹壕，這種方法的時間復(fù)雜度為0(n^2)，且有大量的不必要判斷薇溃。
我們還是考慮一次遍歷的情況菌赖，設(shè)置一個指針i，來尋找從i位置往兩邊擴(kuò)展能擴(kuò)的最大回文子串長度沐序，一次遍歷下來就可以得到答案琉用。但是這時候有個問題，回文串有可能是奇串也有可能是偶串策幼，如果我們分奇偶來考慮則會很麻煩邑时。能否將兩種情況合并成一種呢？我們定義函數(shù)findLongestPalidrome(String s, int i, int j),其中i特姐，j為開始搜索時的起始位置晶丘，那么如果為奇數(shù)的情況下令i＝j(luò)問題就引刃而解了，而偶數(shù)情況下我們令j=i+1到逊，查找de終止條件為i铣口，j越界或者s.charAt(i)!=s.charAt(j)。此時我們可以得到最長的回文子串的開始位置和結(jié)束位置觉壶，用兩個變量記錄下來脑题。然后每一次循環(huán)之后進(jìn)行比較即可。這種情況的復(fù)雜度仍為O(n^2)铜靶，但是中間的判斷步驟會少很多叔遂。可以近似達(dá)到O(n)争剿。
int start = 0;
int len = 1;
public String longestPalindrome(String s) {
if (s == null)
return null;
if (s.length() == 1)
return s;
for (int i = 0; i < s.length(); i++) {
findLongestPalidrome(s, i, i);
findLongestPalidrome(s, i, i + 1);
}
return s.substring(start, start + len);
}
private void findLongestPalidrome(String s, int i, int j) {
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
if (j - i - 1 > len) { //易錯已艰，容易寫成j-i+1
len = j - i - 1;
start = i + 1;
}
}
