LeetCode——5. 最長回文子串

題目描述：【騰訊精選練習（50 題）】

給定一個字元串 

s

，找到 

s

 中最長的回文子串。你可以假設 

s

 的最大長度為 1000。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
           

示例 2：

輸入: "cbbd"
輸出: "bb"
           

解題代碼：

public class RunMain {

	public static void main(String[] args) {
		System.out.println(longestPalindrome("babad"));
		System.out.println(longestPalindrome("cbbd"));
	}

	// 中心擴充算法
	// 我們觀察到回文中心的兩側互為鏡像。是以，回文可以從它的中心展開，并且隻有 2n - 12n−1 個這樣的中心。
	// 為什麼會是 2n - 12n−1 個，而不是 nn 個中心？原因在于所含字母數為偶數的回文的中心可以處于兩字母之間（例如 \textrm{“abba”}“abba” 的中心在兩個 \textrm{‘b’}‘b’ 之間）。
	public static String longestPalindrome(String s) {
		if (s == null || s.length() < 1) return "";
		int start = 0, end = 0;
		for (int i = 0; i < s.length(); i++) {
			int len1 = expandAroundCenter(s, i, i);
			int len2 = expandAroundCenter(s, i, i + 1);
			int len = Math.max(len1, len2);
			if (len > end - start) {
				start = i - (len - 1) / 2;
				end = i + len / 2;
			}
		}
		return s.substring(start, end + 1);
	}

	private static int expandAroundCenter(String s, int left, int right) {
		int L = left, R = right;
		while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
			L--;
			R++;
		}
		return R - L - 1;
	}

}