Longest Palindromic Substring(最长回文子串)

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.

题目的要求是给定一个字符串，找到一个最长的回文子串。

解决这道题首先我们要知道回文字符串的概念，单个字符属于回文字符串，例如"a", 还有另外的形式例如：“baab”, "bab"，其中"bab"包括了单个字符的情况，这两种形式的字符串都是回文字符串。我们可以采用一种中心扩散法来处理这道题，因为有两种不同的形式，因此我们用两种不同的中心扩散法。代码如下：

public class Solution {
    public String longestPalindrome(String s) {
        if(s == null) return "";
        int start = 0;
        int end = 0;
        int max = 0;
        for(int i = 0; i < s.length(); i++) {
            //对应"aba"这种形式的字符串
            int left = i;
            int right = i;
            while(left > -1 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left --;
                right ++;
            }
            if(max < right - left - 1) {
                max = right - left - 1;
                start = left + 1;
                end = right;
            }
            //对应"abba"这种形式的字符串
            left = i;
            right = i + 1;
            while(left > -1 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left --;
                right ++;
            }
            if(max < right - left - 1) {
                max = right - left - 1;
                start = left + 1;
                end = right;
            }
        }
        return s.substring(start, end);
    }
}